题解：P14752 Hit or not?

wanganze · 2025-12-14 19:04:35 · 题解

题意

有一个 n\ (n\le 3000) 边形，一个在 n 边形外部的点沿着 y 轴正方向运动，问打到的第一条边是哪两个点构成的。保证有解。

分析

注意到：虽然取样的点越多，凸多边形近似越精确，但是多边形的顶点数实际很小。

所以我们可以暴力一点，O(n^2)。

首先记录每个点的标号，然后按照 y 从小到大排序，以保证找到的是第一条边。

然后对于一条边，我们的要求是由两个相邻的点构成（注意第一个和最后一个也是相邻的）。如果这条边会被经过，那么 \min(x_1,x_2)<x_0<\max(x_1,x_2)。

实现

#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
struct point
{
    int x,y,id;
    bool operator < (const point &w)
    {
        return y < w.y;
    }
}a[N];
int main()
{
    int n,k;
    cin>>n;
    for(int i = 1; i <= n; i ++) cin>>a[i].x>>a[i].y,a[i].id = i;
    sort(a + 1,a + n + 1);
    cin>>k;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
        {
            if((abs(a[i].id - a[j].id) == 1 || abs(a[i].id - a[j].id) == n - 1) && min(a[i].x,a[j].x) < k && k < max(a[i].x,a[j].x))
            {
                cout<<a[i].id<<' '<<a[j].id<<endl;
                return 0;
            }
        }
    return 0;
}