Codeforces Round #431 (Div. 2) B. Tell Your World（技巧性模拟+精度坑死人系列）

男娘i 2022-06-09 09:50 106阅读 0赞

B. Tell Your World

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

*Connect the countless points with lines, till we reach the faraway yonder.*

There are *n* points on a coordinate plane, the *i*\-th of which being (*i*, *y**i*).

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 *y*1, *y*2, ..., *y**n* ( - 109 ≤ *y**i* ≤ 109) — 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

input

5
    5 4 3 2 1

output

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.

题解：

题意：

给你一堆点，横坐标为点的下标i（从1开始），输入纵坐标，问是否可以用两条平行线贯穿所有的点（不能重合）

思路：

老刘是暴力枚举出所有的斜率k。。。然后a了。。早知道不想了，我的做法还比较复杂，有很多种情况要考虑。。还有就是精度害死人

我的思路：

我取首尾两个点，连接起来，可以发现这条线不是这个平行四边形的对角线就应该是平行四边形的一条边。。。然后就这两种情况模拟

第一种：为平行四边形的边的情况

这个情况比较简单，直接算出斜率，把在直线上的点都vis标记，计算在线上的个数ans

然后再取剩下的2个点（如果只剩一个点那么是Yes）连线看斜率是否也为上面那条线的k，如果是就继续遍历没遍历过的点，如果扫一遍所有点都遍历过了就Yes

否则进行第二种判断

第二种：连线为平行四边形的对角线

这个判断比较复杂，我的思路是取对称点，比如取2的点和n-1处的点，那么这两个点只有两种情况，一是关于对角线对称的点，二是在对角线同一边的点，关于对角线对称的点只要判断下两个点在直线的两边和离对角线垂直的距离是否相等就好了，如果是对角线同一边的点，如果是第一次就记录下两者相加的长度len，如果不是第一次就与len比较，如果距离相加不为len就是错的，输出No，还有是如果是对角线不同边的点但是距离不等就直接No，如果是同一边的点还要加上一个判断与两个端点与1或n处的点3个点要成一条线，最后还要特判中间的点，如果之前有len存在，中间的点的两倍也要等于len，还有就是如果有点在对角线上也是No

ps：

这里的精度特别坑。。。如果是x！=y这种写法，printf是一样的但是系统判断就是不一样。。。所以要写成eps=1e-6（太小了也会判错），abs（x-y）<eps才可以过。。

感觉那么复杂要是知道暴力可以过直接暴力过了

后话：后来我知道了原来只要枚举前三个点组成的k是否符合条件就能求出答案。。。orz

我的很挫的代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-6
    double y[1005];
    int vis[1005];
    int main()
    {
        int tag,i,j,flag,n,ans=2;
        double len,x1,y1,x2,y2,k1,k2,xx,yy;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%lf",&y[i]);
            vis[i]=0;
        }
        x1=1.0,y1=y[1];
        x2=n*1.0,y2=y[n];
        k1=(y2-y1)/(x2-x1);
        vis[1]=1;
        vis[n]=1;
        for(i=2;i<n;i++)
        {
            yy=y[1]+k1*(i-1.0);
            if(yy==y[i])
            {
                ans++;
                vis[i]=1;
            }
        }
        if(ans==n)
        {
            printf("No\n");
            return 0;
        }
        if(ans==n-1)
        {
            printf("Yes\n");
            return 0;
        }
        tag=0;
        for(i=2;i<n;i++)
        {
            if(!vis[i])
            {
                if(tag==0)
                {
                    x1=i;
                    y1=y[i];
                }
                else
                {
                    x2=i;
                    y2=y[i];
                }
                tag++;
                ans++;
                vis[i]=1;
            }
            if(tag==2)
                break;
        }
        k2=(y2-y1)/(x2-x1);
        if(k1==k2)
        {
            for(i=2;i<n;i++)
            {
                if(!vis[i])
                {
                    yy=y1+k2*(i-x1);
                    if(yy==y[i])
                    {
                        ans++;
                        vis[i]=1;
                    }
                    else
                        break;
                }
            }
            if(ans==n)
            {
                printf("Yes\n");
                return 0;
            }
        }
        x1=1,y1=y[1];
        x2=n,y2=y[n];
        tag=0;
        flag=1;
        double yy1,yy2,d1,d2;
        for(i=2;i<=(n+1)/2;i++)
        {
            yy1=k1*(i-1.0)+y1;
            yy2=k1*(n-i)+y1;
            d1=y[i]-yy1,d2=y[n-i+1]-yy2;
            if(d1==0||d2==0)
            {
                flag=0;
                break;
            }
            if(d1*d2<0&&abs(abs(d1)-abs(d2))<eps)
            {
                continue;
            }
            else
            {
                if(d1*d2<0)
                {
                    flag=0;
                    break;
                }
                else
                {
                    if((y[i]-y[1])/(i-1)!=(y[n-i+1]-y[1])/(n-i)&&(y[i]-y[n])/(i-n)!=(y[n-i+1]-y[n])/(1-i))
                    {
                        flag=0;
                        break;
                    }
                }
                if(!tag)
                {
                    tag=1;
                    len=abs(d1)+abs(d2);
                    continue;
                }
                else
                {
                    if(abs(abs(d1)+abs(d2)-len)>eps)
                    {
                        flag=0;
                        break;
                    }
                }
            }
        }
        if(n%2)
        {
            if(tag)
            {
                yy1=k1*((n+1)/2-1.0)+y1;
                d1=y[(n+1)/2]-yy1;
                if(2*abs(d1)!=len)
                    flag=0;
            }
        }
        if(flag)
            printf("Yes\n");
        else
            printf("No\n");
        return 0;
    }