B. Tell Your World（计算几何+思维）

古城微笑少年丶 2021-11-12 00:18 196阅读 0赞

题目链接：[http://codeforces.com/contest/849/problem/B][http_codeforces.com_contest_849_problem_B]

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, 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 ( - 109 ≤ yi ≤ 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  
Copy

5  
7 5 8 6 9

Output  
Copy

Yes

分析：  
题意很简单，把给定的点分成两个直线。  
判断是否在同一条直线上，求K就好。  
我们考虑前三点的情况。  
如果是输出yes的话，只可能是一条直线穿过点a\[1\]和a\[2\]或者a\[1\]和a\[3\]或者a\[2\]和a\[3\]。

所以我们考虑这三条直线的k。我们发现k的值一定为整数或者是一个带0.5的小数。所以不用担心浮点问题。  
我们得到了k。在判断所以在k上的直线情况就可以了。

#include"stdio.h"
    #include"string.h"
    #include"map"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    int n;
    ll a[1010];
    
    int solve(double k)
    {
        int p = -1;
        for(int i = 2; i <= n; i ++)
        {
            if(a[i] - a[1] == (i - 1) * k) continue;
            if(p == -1)
            {
                p = i; continue;
            }
            if(a[i] - a[p] != (i - p) * k) return 0;
        }
        return p != -1;
    }
    
    int main()
    {
        scanf("%d",&n);
        for(int i = 1; i <= n;i ++)
            scanf("%lld",&a[i]);
        int i;
    
        if(solve((double)a[2] - a[1]) || solve((double)a[3] - a[2]) || solve(((double)a[3] - a[1]) / 2.0))
            printf("Yes\n");
        else
            printf("No\n");
    }

[http_codeforces.com_contest_849_problem_B]: http://codeforces.com/contest/849/problem/B