B - Balloon Darts

ytck · 2023-08-04 20:06:08 · 个人记录

三个飞镖把所有气球扎爆

该题的完整详细证明

#include"bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl '\n'
#define x first
#define y second
const int N = 1e4 + 10;
typedef pair<int, int> PII;
typedef complex<int> PT;
int n;
int cross(PT a, PT b)
{
    return imag(conj(a) * b);
}
int cross(PT a, PT b, PT c)
{
    return cross(a - b, b - c);
}

bool solves(vector<PT> s, int depth)
{
    if (s.size() <= 2ll * depth) return true;
    for (int i = 0; i <= depth; i++)
    {
        for (int j = i + 1; j <= depth; j++)
        {
            vector<PT> tmp;
            for (auto item : s)
            {
                if (cross(s[i], s[j], item) != 0) tmp.push_back(item);
            }
            if (solves(tmp, depth - 1)) return true;
        }
    }
    return false;
}

signed main()
{
    cin >> n;
    vector<PT> s(n);//这里不能是n+1，不然我们在solves里的size也是n+1，会错
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        s[i] = { x,y };
    }

    if (solves(s, 3)) cout << "possible" << endl;
    else cout << "impossible" << endl;
}