2014-07-06

UVa 12240 - Cocircular Points

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

Problem

You probably know what a set of collinear points is: a set of points such that there exists a straight line that passes through all of them. A set of cocircular points is defined in the same fashion, but instead of a straight line, we ask that there is a circle such that every point of the set lies over its perimeter.

The International Collinear Points Centre (ICPC) has assigned you the following task: given a set of points, calculate the size of the larger subset of cocircular points.

Input

Each test case is given using several lines. The first line contains an integer N representing the number of points in the set (1$\le$N$\le$100). Each of the next N lines contains two integers X and Y representing the coordinates of a point of the set (- 104$\le$X, Y$\le$104). Within each test case, no two points have the same location.

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

Output

For each test case output a single line with a single integer representing the number of points in one of the largest subsets of the input that are cocircular.

Sample Input

7 
-10 0 
0 -10 
10 0 
0 10 
-20 10 
-10 20 
-2 4 
4 
-10000 10000 
10000 10000 
10000 -10000 
-10000 -9999 
3 
-1 0 
0 0 
1 0 
0

Sample Output

1
2
3

5 
3 
2

Solution

題目描述：

給平面上 n 個點，最多有多少個點共圓？

題目解法：

窮舉三點拉外心，隨後找共圓的點，最慘會到 O(n^4)。

完全沒有剪枝，也就是說可以刻意將點保留標記，防止窮舉到相同組合，又或者是先按照 x 軸排序，直接在區間內搜索可能的共圓點之類的。

#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double a) const {
        return Pt(x/a, y/a);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dist2(Pt a, Pt b) {
    return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
    double a1, a2, b1, b2, c1, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
    a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
    d = a1 * b2 - a2 * b1;
    dx = b2 * c1 - b1 * c2;
    dy = a1 * c2 - a2 * c1;
    return Pt(dx / d, dy / d);
}
Pt circle(Pt a, Pt b, Pt c) {
    Pt mab = (a + b)/2;
    Pt mbc = (b + c)/2;
    Pt lab = b - a, lbc = c - b;
    swap(lab.x, lab.y);
    swap(lbc.x, lbc.y);
    lab.x = -lab.x;
    lbc.x = -lbc.x;
    return getIntersection(mab, lab, mbc, lbc);
}
int main() {
    int n;
    Pt D[128];
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++) {
            scanf("%lf %lf", &D[i].x, &D[i].y);
        }
        int ret = min(2, n);
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                for(int k = j + 1; k < n; k++) {
                    if(fabs(cross(D[i], D[j], D[k])) < eps)
                        continue;
                    Pt o = circle(D[i], D[j], D[k]);
//					printf("%lf %lf %lf %lf %lf %lf\n", D[i].x, D[i].y, D[j].x, D[j].y, D[k].x, D[k].y);
//					printf("circle %lf %lf\n", o.x, o.y);
                    double d = dist2(o, D[i]);
                    int cnt = 0;
                    for(int p = 0; p < n; p++) {
                        if(fabs(d - dist2(D[p], o)) < eps)
                            cnt++;
                    }
                    ret = max(ret, cnt);
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

Morris' Blog