题目连接 codeforces 961.D
题意:
给出若干个点,问是否能画出两条线,保证这些点都在这两条线上
题解:
两点确定一条直线,找出一点不在这条直线上,然后枚举这三个点两两在一条直线上,如果有出现第5个点不在这两条直线上(因为出现第4个点时,虽然不在第一条直线上,但是可以和第3个不在第一条直线上的点组成第二条直线),输出NO,否则输出YES
向量叉乘 等于 0 ,三点在同一条直线上 (x1 * y2) - (x2 * y1)
#include <bits/stdc++.h>typedef long long ll;using namespace std;struct node{ll x, y;}a[100005];int n;ll cross(int d, int b, int c){ // 向量叉乘return (a[d].x-a[b].x) * (a[c].y-a[b].y) - (a[c].x-a[b].x) * (a[d].y-a[b].y);}bool judge(int a, int b){int c = -1, d = -1;for(int i = 1; i <= n; i++){if(cross(a, b, i) != 0){if(c == -1){c = i; // 出现第3个点不在第一条直线上}else if(d == -1){d = i; // 出现第4个点不在第一条直线上}else if(cross(c, d, i) != 0){ // 第三个和第四个点组成第二条直线return false; // 都不在这两条直线上,这种情况不成立}}}return true;}int main(){int c = -1;cin >> n;for(int i = 1; i <= n; i++){cin >> a[i].x >> a[i].y;}for(int i = 3; i <= n; i++){if(cross(1, 2, i) != 0){c = i; // 出现不在第一条直线上的点break;}}if(c == -1){// 如果没有出现,说明全部点都在一条直线上,符合题意cout << "YES" << endl;}else if(judge(1, 2) || judge(1, c) || judge(2, c)){ // 枚举三个点两两在一条直线上cout << "YES" << endl;}else{cout << "NO" << endl;}return 0;}