[CF961D] Pair Of Lines

[CF961D] Pair Of Lines - 计算几何

Description

在平面直角坐标系上给出(n)个点，求是否存在两条直线穿过所有点。

Solution

对于任意三个点，其中必有两个在同一条直线上

随便取三个点，枚举其中哪两个在一条直线上，然后找出直线外的点，判断它们是否也在一条直线上

#include <bits/stdc++.h>
using namespace std;

#define int long long

// todo: geometry (3')

struct vec2
{
    int x, y;
    vec2 operator+(const vec2 &rhs) const
    {
        return {x + rhs.x, y + rhs.y};
    }
    vec2 operator-(const vec2 &rhs) const
    {
        return {x - rhs.x, y - rhs.y};
    }
    int operator%(const vec2 &rhs) const
    {
        return x * rhs.y - y * rhs.x;
    }
};

// todo: check p,q,r (2')

bool sameline(vec2 p, vec2 q, vec2 r)
{
    vec2 a = p - q;
    vec2 b = q - r;
    return a % b == 0;
}

//////////////////////////

int n;
vec2 p[100005];

// todo: give i,j, check (5')

bool check(int i, int j)
{
    vector<vec2> res;
    // remove all on pi,pj
    for (int k = 1; k <= n; k++)
    {
        if (i == k || j == k)
            continue;
        if (sameline(p[i], p[j], p[k]))
            continue;
        res.push_back(p[k]);
    }
    // check if on same line
    if (res.size() < 3)
        return true;
    auto x = res[0], y = res[1];
    for (int k = 2; k < res.size(); k++)
    {
        if (!sameline(x, y, res[k]))
            return false;
    }
    return true;
}

// todo: main (3')

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i].x >> p[i].y;

    if (n <= 4 || check(1, 3) || check(2, 3) || check(1, 2))
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}