2014-07-06

UVa 12194 - Isosceles Triangles

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

A given triangle can be either equilateral (three sides of the same length), scalene (three sides of different lengths), or isosceles (two sides of the same length and a third side of a different length). It is a known fact that points with all integer coordinates cannot be the vertices of an equilateral triangle.

You are given a set of different points with integer coordinates on the XY plane, such that no three points in the set lay on the same line. Your job is to calculate how many of the possible choices of three points are the vertices of an isosceles triangle.

Input

There are several test cases. Each test case is given in several lines. The first line of each test case contains an integer N indicating the number of points in the set (3$\le$N$\le$1000). Each of the next N lines describes a different point of the set using two integers X and Y separated by a single space (1$\le$X, Y$\le$106); these values represent the coordinates of the point on the XY plane. You may assume that within each test case no two points have the same location and no three points are collinear.

The last test case is followed by a line containing a single zero.

Output

For each test case output a single line with a single integer indicating the number of subsets of three points that are the vertices of an isosceles triangle.

Sample Input

5 
1 2 
2 1 
2 2 
1 1 
1000 1000000 
6 
1000 1000 
996 1003 
996 997 
1003 996 
1003 1004 
992 1000 
0

Sample Output

1
2

4
10

Solution

題目描述：

給平面 N 個點，任挑三個點有多少以某個節點為頂點的等腰三角形。

題目解法：

直接對單一頂點找到對於其他頂點的的所有距離，排序後找重複的長度進行組合計算，將複雜度 O(n^3) 降到 O(n^2 log n)

#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
    int N;
    long long X[1024], Y[1024];
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 0; i < N; i++)
            scanf("%lld %lld", &X[i], &Y[i]); 
        long long d[1024];
        long long ret = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++)
                d[j] = (X[i] - X[j]) * (X[i] - X[j]) +
                        (Y[i] - Y[j]) * (Y[i] - Y[j]);
            sort(d, d+N);
            long long cnt = 1;
            d[N] = -1;
            for(int j = 1; j <= N; j++) {
                if(d[j] != d[j-1]) {
                    ret += cnt * (cnt-1) /2;
                    cnt = 1;
                } else {
                    cnt++;
                }
            } 
        }
        printf("%lld\n", ret);
    }
    return 0;
}

Morris' Blog