ArepitaDePernil's blog

Isosceles Triangles — Latin America Regional 2009 problem
By ArepitaDePernil, 9 years ago, In English

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! :)

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it 

    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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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;

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        sort(b, b + len) is NLogN, so total complexity is N^2LogN

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thank you very much, now i fully understand the solution to the problem :)

        → Reply