题解：P16864 [GKS 2021 #G] Simple Polygon

zhangleyi0417 · 2026-07-21 11:52:26 · 题解

构造题，看着挺简单的。

题意

给定 n，A，构造一个 N 个顶点的简单多边形，使其面积的两倍为 A。无解输出 IMPOSSIBLE。

思路

我们先考虑无解情况，由皮克定理 \frac{A}{2}=S=n+\frac{s}{2}-1, S 为顶点均为整点的简单多边形的面积，n 为内部格点数目，s 为边界个点数目。又因为 0\le n，N \le s，所以 \frac{A}{2}\ge \frac{n}{2}-1 即 A\ge n-2。故当 A<n-2 时输出 IMPOSSIBLE。

对于 A\ge n-2 的情况我们同楼上题解，先如图构造 S=\frac{n}{2}-1。

然后对于 y\ge 1 为了简化问题，我们考虑不变，只变下半部分，则 S_{x<1}=\frac{1}{2}(1+l)=\frac{A}{2}-n+2 (l 为底长 )，所以 l=A-n+3。

规律很好找，就不给了，不会看代码。

:::info[ACcode(c++)] 就知道你会点开

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        int n,a;
        cin>>n>>a;
        if(n-2>a)
        {
            cout<<"Case #"<<i<<": IMPOSSIBLE\n";
            continue;
        }
        cout<<"Case #"<<i<<": POSSIBLE\n";
        for(int j=0;j<=(n-2)/2;j++)cout<<j%2<<" "<<j<<"\n";
        if(n&1)cout<<(n-2)%2<<" "<<(n-1)/2<<"\n";
        for(int j=(n-2)/2;j>=1;j--)cout<<j%2+1<<" "<<j<<"\n";
        cout<<a+3-n<<" "<<0<<"\n";
    }
    return 0;
}

:::