Codeforces 961 D Pair Of Lines

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目描述

You are given nn points on Cartesian plane. Every point is a lattice point (i. e. both of its coordinates are integers), and all points are distinct.

You may draw two straight lines (not necessarily distinct). Is it possible to do this in such a way that every point lies on at least one of these lines?

输入输出格式

输入格式：

The first line contains one integer nn (1<=n<=10^{5})(1<=n<=105) — the number of points you are given.

Then nn lines follow, each line containing two integers x_{i}xi and y_{i}yi (|x_{i}|,|y_{i}|<=10^{9})(∣xi∣,∣yi∣<=109) — coordinates of ii -th point. All nn points are distinct.

输出格式：

If it is possible to draw two straight lines in such a way that each of given points belongs to at least one of these lines, print YES. Otherwise, print NO.

输入输出样例

输入样例#1：

输出样例#1：

YES

输入样例#2：

输出样例#2：

NO

说明

In the first example it is possible to draw two lines, the one containing the points 11 , 33 and 55 , and another one containing two remaining points.

一个很显然的性质是，任意三个点中至少有两个在同一条直线上。

也就是说，在一个可行的方案中，至少有一条线是经过点1-点2 或者点2-点3 或者点1-点3 构成的直线的，所以我们直接做就行了。。。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=100005;

int px[maxn],py[maxn],n;

int dx,dy,now;

bool tag[maxn];

inline bool check(int x,int y){

	memset(tag,0,sizeof(tag));

	tag[x]=tag[y]=1,now=x;

	dx=px[x]-px[y],dy=py[x]-py[y];

	for(int i=1;i<=n;i++) if(!tag[i])

	    if(dx*(ll)(py[i]-py[now])==dy*(ll)(px[i]-px[now])) tag[i]=1;

	bool flag=1;

	for(int i=1;i<=n;i++) if(!tag[i]){

		for(int j=i+1;j<=n;j++) if(!tag[j]){

			dx=px[j]-px[i],dy=py[j]-py[i],now=i;

			for(int l=j+1;l<=n;l++) if(!tag[l]&&dx*(ll)(py[l]-py[now])!=dy*(ll)(px[l]-px[now])) flag=0;

			break;

		}

		break;

	}

	return flag;

}

inline void solve(){

	if(n<=4){

		puts("YES");

		return;

	}

	if(check(1,2)||check(1,3)||check(2,3)) puts("YES");

	else puts("NO");

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d%d",px+i,py+i);

	solve();

	return 0;

}