bupt|118. Three Points On A Line-蒲公英云

bupt|118. Three Points On A Line

时间限制 1000 ms 内存限制 65536 KB

题目描述
Given points on a 2D plane, judge whether there’re three points that locate on the same line.

输入格式
The number of test cases T(1≤T≤10) appears in the first line of input.

Each test case begins with the number of points N(1≤N≤100). The following N lines describe the coordinates (xi,yi) of each point, in accuracy of at most 3 decimals. Coordinates are ranged in [−104,104].

输出格式
For each test case, output Yes if there’re three points located on the same line, otherwise output No.
对于每个测试用例，如果有三个点位于同一行，则输出Yes，否则输出No。

输入样例

2
3
0.0 0.0
1.0 1.0
2.0 2.0
3
0.001 -2.000
3.333 4.444
1.010 2.528

输出样例

Yes
No
#include<bits/stdc++.h>
using namespace std;
int main() { 
    int t, n;
    float a[105];
    float b[105];
    while(scanf("%d", &t) != EOF) { 
        while(t--) { 
            int flag = 0;
            scanf("%d", &n);
            for(int i = 0; i < n; i++) { 
                scanf("%f", &a[i]);
                scanf("%f", &b[i]);
            }
            for(int i = 0; i < n && !flag; i++) { 
                for(int j = i + 1; j < n && !flag; j++) { 
                    for(int k = j + 1; k < n && !flag; k++) { 
                        if((b[k] - b[j]) / (a[k] - a[j]) == (b[j] - b[i]) / (a[j] - a[i])) { 
                            flag = 1;
                        }
                    }
                }
            }
            if(flag == 1) { 
                printf("Yes\n");
            } else { 
                printf("No\n");
            }
        }
    }
    return 0;
}