HDU 1432 Lining Up（几何）

 1 #include<cstdio>
 2 
 3 struct Point{
 4     int x, y;
 5 
 6     Point(int x = 0, int y = 0): x(x), y(y){}
 7 
 8     void scan(){
 9         scanf("%d%d", &x, &y);
10     }
11 };
12 
13 typedef Point Vector;
14 
15 Vector operator - (Vector A, Vector B){//重载结构体减号
16     return Vector(A.x - B.x, A.y - B.y);
17 }
18 
19 int cross(Vector A, Vector B){//叉乘
20     return A.x * B.y - A.y * B.x;
21 }
22 
23 Point p[700];
24 int n;
25 
26 int main(){
27     while(~scanf("%d", &n)){
28         for(int i = 0; i < n; ++i){
29             p[i].scan();
30         }
31 
32         int best = 0;//记录直线穿过最多的点个数
33         for(int i = 0; i < n; ++i){
34             for(int j = i + 1; j < n; ++j){
35                 int num = 2;//因为直线穿过i和j点，所以直线上已经有两个点了
36                 for(int k = j + 1; k < n; ++k){
37                     if(!cross(p[i] - p[j], p[i] - p[k])){//判断点k在直线ij上
38                         ++num;
39                     }
40                 }
41                 if(best < num){//更新最优值 
42                     best = num;
43                 }
44             }
45         }
46         printf("%d\n", best);
47     }
48     return 0;
49 }