cf Educational Codeforces Round 41 D. Pair Of Lines

原题：
D. Pair Of Lines
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given n 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?

Input
The first line contains one integer n (1 ≤ n ≤ 105) — the number of points you are given.

Then n lines follow, each line containing two integers xi and yi (|xi|, |yi| ≤ 109)— coordinates of i-th point. All n points are distinct.

Output
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.

Examples
input
5
0 0
0 1
1 1
1 -1
2 2
output
YES
input
5
0 0
1 0
2 1
1 1
2 3
output
NO

Note
In the first example it is possible to draw two lines, the one containing the points 1, 3 and 5, and another one containing two remaining points.

中文：

给你一堆点，判断能否用两个直线把这些点都连接起来。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;


const int maxn = 100001;

struct Point
{
    ll x,y;
    ll rx,ry;//根据原点对称后的点
    Point(ll x = 0, ll y = 0) :x(x), y(y){}
};

typedef  Point Vector;

bool line(const Point &p1, const Point &p2, const Point &p3)//判断三点是否共线
{
    return (p3.y - p1.y)*(p2.x - p1.x) - (p2.y - p1.y)*(p3.x - p1.x)==0;
}

ll Cross(Vector A, Vector B)//叉积
{
    return A.rx*B.ry - A.ry*B.rx;
}


bool cross_cmp(const Vector &a,const Vector &b)
{
    if(Cross(a,b)==0)//在一条直线上是等于0
        return a.rx<b.rx;
    else
        return Cross(a,b)<0;
}

int n;
vector<Point> v,one,two,three;



bool solve(Point o,vector<Point> V)
{
    sort(V.begin(),V.end(),cross_cmp);

    vector<Point> tmp;

    int ind = 0,ans=0,pre=0;
    for (int i = 0; i < V.size();)
    {
        int j = i + 1;
        while (j <V.size())
        {
            if (Cross(V[i], V[j])==0)
                j++;
            else
                break;
        }
        if (j - i> ans +1 )
        {
            ans = j - i;//不算上原点
            pre = i;
            ind = j - 1;
        }
        i = j;
    }



    if(ans==0)
        return false;

    for (int i = 0; i < V.size(); i++)
        {
            if (i<pre || i>ind)//去除在一个极角上的点
                tmp.push_back(V[i]);
        }


        if (tmp.size() <= 2)
            return true;
        for (int i = 2; i < tmp.size(); i++)//剩下的点是否在一条直线
        {
            if (!line(tmp[i-2], tmp[i-1], tmp[i]))
                return false;
        }
    return true;

}
void trans(Point &p)//如果一个点在三，四象限或者在x轴负方向上，那么找到这个点关于原点的对称点
{
    if(p.ry<0||(p.ry==0&&p.rx<0))
    {
        p.rx=-p.rx;
        p.ry=-p.ry;
    }
}

int main()
{

    ios::sync_with_stdio(false);
    Point tmp,a,b,c;
    while (cin >> n)
    {
        v.clear();
        one.clear();
        two.clear();
        three.clear();
        for (int i = 0; i < n; i++)
        {
            cin >> tmp.x >> tmp.y;
            v.push_back(tmp);
        }
        if (n <= 4)
        {
            cout << "YES" << endl;
            continue;
        }
        a = v[0];
        b = v[1];
        c = v[2];
        for (int i = 0; i < v.size(); i++)
        {
            if (i != 0)//以第一个点为原点
            {
                tmp.x = v[i].x - a.x;
                tmp.y = v[i].y - a.y;
                tmp.rx=tmp.x,tmp.ry=tmp.y;
                trans(tmp);
                one.push_back(tmp);
            }
            if (i != 1)//以第二个点为原点
            {
                tmp.x = v[i].x - b.x;
                tmp.y = v[i].y - b.y;
                tmp.rx=tmp.x,tmp.ry=tmp.y;
                trans(tmp);
                two.push_back(tmp);
            }
            if (i != 2)//以第三个点为原点
            {
                tmp.x = v[i].x - c.x;
                tmp.y = v[i].y - c.y;
                tmp.rx=tmp.x,tmp.ry=tmp.y;
                trans(tmp);
                three.push_back(tmp);
            }
        }


        if (solve(a, one) || solve(b, two) || solve(c, three))
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }

    }
    return 0;
}

解答：

此题思路倒是不难，代码有点麻烦，应该是我处理的不够好。

首先可以肯定的是，如果点少于4个，那么肯定能用两条直线串起来。

如果大于4个点，那么任取一个点作为原点，把所有点按照极角排序，角度相同的点，一定是在一条直线上的，找出角度相同最多的点，把这些点连上，作为第一条线。去掉第一条线上的点，判断剩下的点是否在一条线就完活。
如图

不过仅仅使用一个点作为原点来计算所有点的极角有这样一个问题，如果选取作为原点的点计算极角后，所有的角度都不一样，那是不是不能使用两个直线来连接？答案是否定的，因为会出现下面图中的情况。

红点表示在一条直线上的点，有两个，而且其中一个作为原点，黑点在另外一条直线上。可以看到，以其中任意一个红点作为原点，最后得到的极角都是不一样的，所以，起码要枚举三个点来作为原来判断。

在使用极角排序的过程中，使用的是叉积，使用叉积能够避免角度的问题，使用叉积来进行极角排序，只是判断以原点为起点，连接的两个点的向量，哪个在“左侧”，哪个在“右侧”，而且还有另外一个问题，那就是使用叉积得到的结果会有负值。

所以，这里将所有在三四象限以及在x轴负方向上的点画到原点对称的点上去，这样不会影响结果，因为如果一个点是和原点在一条直线上的点，那么关于原点对称的点也绝对在这个直线上，这样就可以枚举了。