CodeForces - 961D(两线过点)
程序员文章站
2022-04-02 16:52:42
...
题意:给出一些点,问是否能用两条直线全部通过这些点。
题解:找出不共线的三点,可确定三条直线,依次枚举三条直线是否符合条件即可。
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-8;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n;
long long x[maxn], y[maxn];
long long cross(int i, int j, int k)
{
long long dx1 = x[j] - x[i];
long long dy1 = y[j] - y[i];
long long dx2 = x[k] - x[i];
long long dy2 = y[k] - y[i];
return dx1 * dy2 - dy1 * dx2;
}
bool judge(int a, int b) //如不在直线ab上,则会产生新的直线cd,如不在则失败
{
int c = -1;
int d = -1;
for(int i = 0; i < n; i++){
if(cross(a, b, i) != 0){
if(c == -1) c = i;
else if(d == -1) d = i;
else if(cross(c, d, i) != 0) return false;
}
}
return true;
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%lld%lld", &x[i], &y[i]);
int a = 0;
int b = 1;
int c = -1;
for(int i = 2; i < n; i++){
if(cross(a, b, i) != 0){
c = i; break;
}
}
if(c == -1) puts("YES");
else if(judge(a, b) || judge(a,c) || judge(b, c)) puts("YES");
else puts("NO");
return 0;
}