题解：P13667 [GCPC 2023] Balloon Darts

Solution

确定性做法。

先随便找四个点，其中肯定至少有两个点是在一条答案直线上的，于是枚举这条直线，其有 $\binom{4}{2} = 6$ 种可能性。然后把在这条直线上的点都去掉，这样还有两条要确定的直线。再随便找三个点，其中至少有两个点在一条答案直线上，枚举这条直线，然后再去掉这条直线上的点，然后判一下剩下的点在不在同一条直线上即可。

复杂度是 $O(n)$，带一些很大的常数。

Code

代码是模拟赛场上写的，可能有点一坨。

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long 
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define REP(i, l, r, k) for (int i = (l); i <= (r); i += k)
#define PER(i, l, r, k) for (int i = (l); i >= (r); i -= k)
#define ls x << 1
#define rs x << 1 | 1
#define umap unordered_map
#define uset unordered_set
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define x1 Sun
#define y1 Jude
void ckmin(int &x, int y) { x = std::min(x, y) ; }
void ckmax(int &x, int y) { x = std::max(x, y) ; }
int lowbit(int x) { return x & -x ; }

using namespace std;

const int maxn = 1e4 + 5 ;
// const int inf = ;
// const int mod = ; 

int n ;
struct Node {
    int x, y ;
} a[maxn] ;

int ck(int x, int y, int z) {
    return ((a[x].y - a[y].y) * (a[x].x - a[z].x) == (a[x].y - a[z].y) * (a[x].x - a[y].x)) ;
}

bool vis[maxn] ;

void solve(){
    cin >> n ;
    rep(i, 1, n) {
        cin >> a[i].x >> a[i].y ;
     }
     if(n <= 3) {
         cout << "possible\n" ;
         return ;
     } 
     rep(i, 1, 4) {
         rep(j, i + 1, 4) {
             if(i == j) continue ;
             rep(i, 1, n) vis[i] = 0 ;
             vis[i] = vis[j] = 1 ;
            rep(k, 1, n) {
                if(ck(i, j, k)) vis[k] = 1 ;
            }
            vector<int> id1 ;
            rep(k, 1, n) {
                if(!vis[k]) id1.pb(k) ;
                if(id1.size() == 4) break ;
            }
            if(id1.size() <= 3) {
                cout << "possible\n" ;
                return ;
            } 
            rep(m, 0, id1.size() - 1) {
                rep(nn, m + 1, id1.size() - 1) {
                    int M = id1[m], N = id1[nn] ;
                    if(M == N) continue ;
                    vis[M] = vis[N] = 1 ;
                    vector<int> cl ;
                    rep(l, 1, n) {
                        if(ck(M, N, l) && !vis[l]) {
                            vis[l] = 1 ;
                            cl.pb(l) ;
                        }
                    }        
                    vector<int> id2 ;
                    rep(l, 1, n) {
                        if(!vis[l]) id2.pb(l) ;
                    }        
                    if(id2.size() <= 2) {
                        cout << "possible\n" ;
                        return ;
                    }
                    bool fnd = 1 ;
                    rep(X, 2, id2.size() - 1) {
                        if(!ck(id2[0], id2[1], id2[X])) {
                            fnd = 0 ;
                        }
                    }
                    if(fnd) {
                        cout << "possible\n" ;
                        return ;
                    }
                    vis[M] = vis[N] = 0 ;
                    for(auto cle : cl) vis[cle] = 0 ;
                }
            }
         }
     }
     cout << "impossible\n" ;
    return ;
}
signed main(){
    // freopen("balloon.in", "r", stdin) ;
    // freopen("balloon.out", "w", stdout) ;
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1 ; 
    // cin >> T ;
    while(T -- ){
        solve() ;
    }
    return 0 ;
} 

---

• 分类： OI
• 标签： 无标签