B. Tell Your World Codeforces Round #431(Div.2)(간단한 시뮬레이션)
There are n points on a coordinate plane, the i-th of which being (i, yi).
Determine whether it’s possible to draw two parallel and non-overlapping lines, such that every point in the set lies on exactly one of them, and each of them passes through at least one point in the set.
Input The first line of input contains a positive integer n (3 ≤ n ≤ 1 000) — the number of points.
The second line contains n space-separated integers y1, y2, …, yn ( - 10^9 ≤ yi ≤ 10^9) — the vertical coordinates of each point.
Output Output “Yes” (without quotes) if it’s possible to fulfill the requirements, and “No” otherwise.
You can print each letter in any case (upper or lower).
Examples input 5 7 5 8 6 9 output Yes input 5 -1 -2 0 0 -5 output No input 5 5 4 3 2 1 output No input 5 1000000000 0 0 0 0 output Yes Note In the first example, there are five points: (1, 7), (2, 5), (3, 8), (4, 6) and (5, 9). It’s possible to draw a line that passes through points 1, 3, 5, and another one that passes through points 2, 4 and is parallel to the first one.
In the second example, while it’s possible to draw two lines that cover all points, they cannot be made parallel.
In the third example, it’s impossible to satisfy both requirements at the same time.
대체적인 제목: 2차원 평면에 n개의 점이 있다. 이 n개의 점의 좌표를 알려주고 두 개의 겹치지 않는 평행선을 찾아서 모든 점, 한 부분은 한 라인에 있고 다른 한 부분은 다른 라인에 있다.
사고방식: 모든 점 x 좌표가 다르기 때문에 두 점을 통과하는 직선의 사율은 반드시 존재한다.조건을 충족시키는 두 개의 평행선 a, b가 존재한다고 가정하면 모든 점은 직선 a가 아니라 직선 b에 있다. 그래서 우리는 먼저 1호점과 다른 모든 점의 사율을 구한 다음에 그 중에서 하나의 사율 k를 현재의 평행선의 사율로 선택할 수 있다.다음에 모든 점을 두루 훑어본다. 만약에 어떤 점과 1호점의 사율이 k가 아니라면 이 점은 다른 평행선에 있어야 한다. 기록한 다음에 이 점들이 다른 평행선을 구성할 수 있는지 판단하고 사율이 k이다.구체적으로 실현하려면 코드를 보아라.주의: 모든 점이 같은 직선에 있으면 안 됩니다.
코드는 다음과 같다.
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int a[1005];// ,
double ans[1005];// 2~n 1
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(i!=1)
{
ans[i]=(a[i]-a[1])*1.0/(i-1);
}
}
int flag1=0;
for(int i=2;i<=n;i++)
{
double k1=ans[i];//
int f=0;//
int x;
int flag2=1;
for(int j=2;j<=n;j++)//
{
if(j==i)
continue;
if(ans[j]!=k1)// j 1 k1,
{
if(f==0)//
{
x=j;
f++;
}
else// j k1
{
f++;
if((a[j]-a[x])*1.0/(j-x)!=k1)// k1, i 1 , ,
{
flag2=0;
break;
}
}
}
}
if(f==0)//
{
printf("No
");
return 0;
}
if(flag2)// ,
{
flag1=1;
break;
}
}
if(flag1)
printf("Yes
");
else // 1 ,
{
double k=(a[3]-a[2])*1.0;
for(int i=4;i<=n;i++)
{
if((a[i]-a[2])*1.0/(i-2)!=k)
{
printf("No
");
return 0;
}
}
printf("Yes
");
}
}