Блог пользователя ArepitaDePernil

Isosceles Triangles — Latin America Regional 2009 problem
Автор ArepitaDePernil, 10 лет назад, По-английски

Hello, i have been trying to solve this problem for quite a while, i am aware this is kind of a standar geometry/counting problem. However the logic behind the solutions i read its pretty unclear to me, and since there is not outline at all, i decided to ask for the help of the CF community.

Ok, so instead of dropping the link to the statement i'll explain the problem, you are given a set of points (which are less than 1000 points), your task is to tell in how many ways you can combine those points to make an isosceles triangle (no three points are collinear) . I have found many problems that follow this concept, and they just change the number of vertices, so i am pretty sure i want to understand the solution to the problem.

if you can help me, that would be great, thanks! :)

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится 

    long long ans = 0;
    for (int i = 0; i < n; i++) { //bruteforce vertex (a[i])
        map<long long, int> M;
        set<pair<int,int> > S;
        long long cnt = 0;
        for (int j = 0; j < n; j++) {
            int x = a[j].first - a[i].first;
            int y = a[j].second - a[i].second;
            long long d = 1ll * x * x + 1ll * y * y;
            cnt += M[d]; //number of previous points, we can choose a pair of a [j]
            cnt -= (int)(S.find(make_pair(a[i].first - x, a[i].second - y)) != S.end()); //if one of them colinear
            M[d]++;
            S.insert(a[j]);
        }
        ans += cnt;
    }
    cout << ans << endl;

This solution works, if there is no coinciding points, and all coordinates are integers.

Sorry for my poor english

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    it's a pretty short code O: , i know you count the number of equal distances, however i don't know how it works if you don't check that the side with a different distance connects them ): can you explain me your code?

    Edit: I tested the code and gives TLE, this is the statement :

    https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2481

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Firstly, the equilateral triangle can not have integer coordinates of vertices.

      Isosceles triangle has two equal sides. These sides have a common vertex. Choose this vertex. After iterate other points. For each point, determine how many of previouse we can use in common base.

      One of vesion of this task on russian site.

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      You explained harder version of that problem. In your expalaration to make an isosceles triangle (no three points are collinear) I can put on trinagles like (2, 2) (1, 1) (0, 0) prohibited.

      In statement: within each test case no three points are collinear.

      modified code:

              long long ans = 0;
        for (int i = 0; i < n; i++) { //bruteforce vertex (a[i])
            map<long long, int> M;
            long long cnt = 0;
            for (int j = 0; j < n; j++) {
                int x = a[j].first - a[i].first;
                int y = a[j].second - a[i].second;
                long long d = 1ll * x * x + 1ll * y * y;
                cnt += M[d]++; //number of previous points, we can choose a pair of a [j]
            }
            ans += cnt;
        }
        cout << ans << endl;

      But it so slow. (map has big constant)

      Faster version, which doing same: 

              long long ans = 0;
        for (int i = 0; i < n; i++) {
            int len = 0;

            for (int j = 0; j < n; j++) {
                if (j != i) {
                    b[len++] = sqr(x[i] - x[j]) + sqr(y[i] - y[j]);
                }
            }
            sort(b, b + len);
            b[len] = 1ll << 60;
            for (int j = 0; j < len;) {
                int d = 0;
                while (b[j] == b[j + d]) {
                    d++;
                }
                ans += d * (d - 1) / 2;
                j = j + d;
            }
        }
        cout << ans << endl;

      → Ответить