2022CCPC Weihai Site C. Grass

C. Grass

题意：

选出5个点，并以A点为中心不存在与其他4个点的向量同向且共线

分析：

预选出4个点，枚举第5个点

• 如果遍历一遍后没有找到能与选定的4个点不都同向共线，此时一定满足所有的点都共线（所有点都不满足）

当选出满足条件的点后再去判断以那个点为中心去连接其他点不会有共线的情况：

• 这里判断共线使用叉积 \(\frac{x_1}{y_1} = \frac{x_2}{y_2}\) 判断是否共线，
• 判断是否同向用叉乘，不同向则叉乘为负

实现：

#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2000010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
int T;
int n;
struct Point
{
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y){};
} p[N], res[6], tmp[6];
Point operator-(Point A, Point B)
{
    return {A.x - B.x, A.y - B.y};
}
bool operator*(Point A, Point B)
{
    if (B.x * A.y != B.y * A.x)
        return 0;
    if (B.x * A.x < 0 || B.y * A.y < 0)
        return 0;
    return 1; // 两向量同向且共线
}
bool check()
{
    for (int i = 1; i <= 5; i++)
    {
        int idx = 0;
        for (int j = 1; j <= 5; j++)
        {
            if (i != j)
                tmp[++idx] = res[i] - res[j];
        }

        bool f = true;
        for (int j = 1; j <= 4 && f; j++)
        {
            for (int k = 1; k <= 4 && f; k++)
            {
                if (j != k && (tmp[j] * tmp[k]))
                    f = false;
            }
        }
        if (!f)
            continue;

        cout << "YES" << endl;
        cout << res[i].x << " " << res[i].y << endl;
        for (int j = 1; j <= 5; j++)
        {
            if (i != j)
                cout << res[j].x << " " << res[j].y << endl;
        }
        return 1;
    }
    return 0;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i].x >> p[i].y;

    if (n < 5)
    {
        cout << "NO" << endl;
        return;
    }
    else
    {
        for (int i = 1; i <= 4; i++)
            res[i] = p[i];

        for (int i = 5; i <= n; i++)
        {
            res[5] = p[i];
            if (check())
                return;
        }
        cout << "NO" << endl;
    }
}
signed main()
{
    FAST;
    T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}