#3374. 「eJOI2020」三角剖分 题解

· · 题解

显然可以顺着枚举一遍。

预计得分10分。

#include "triangulation.h"
#include <iostream>

using namespace std;

int solve(int n)
{
    cin>>n;
    int i,j,k;
    for(i=2;i<=n;i++)
    {
        for(j=1;j<=i-1;j++)
        {
            if(query(j,n-i+j)==1)
            {
                return j*n+n-i+j;
            }
        }
    }
}

画图分析会发现：

一定有线段AB除非点A到B中有点与0有线段或AB距离为1。

显然AB上方的线段到0的距离一定大于AB到0的距离。

因此只需将2到(n-1)是否与0有线问一遍即可。

最后记得特判。

代码：

#include "triangulation.h"
#include <iostream>

using namespace std;

int d(int a,int b)
{
    if(a!=0)
    {
        return max(a,n-b);
    }
    else 
    {
        return max(b,n-b);
    }
}
int query(int a,int b)
{
    int x;
    cin>>x;
    return x;
}
int solve(int n)
{
    cin>>n;
    int i;
    int dis=9999999,ans=0;
    int l=1;
    for(i=2;i<=n-1;i++)
    {
        if(query(i,0)==1)
        {
            if(d(i,0)<dis)
            {
                dis=d(i,0);
                ans=i;
            }
            if(i-l>1&&d(l,i)<dis)
            {
                dis=d(l,i);
                ans=n*l+i;
            }
            l=i;
        }
    }
    int i=n-1;
    if(l+1!=i&&d(l,n-1)<ans)
    {
    dis=d(l,n-1);
    ans=n*l+n-1;
    }
    return ans;
}