题解 P1227 【[JSOI2008]完美的对称】

盖矣斌峥 · 2019-06-11 10:01:21 · 题解

本人博客

我们将点按照一定顺序排序（按x、y从小到大、从大到小都行） //作者是按照y从小到大排的

然后很容易能想到y最小的一定是和y最大的进行匹配

所以就遍历一遍已经排好的序列，用求中点的公式求出中点（相信大家都会）

    point tmp;
    tmp.x=(a[i].x+a[n-i+1].x)/2.0;
    tmp.y=(a[i].y+a[n-i+1].y)/2.0;

再判断一下每组匹配的中点是否一样就行了

因为n有可能是奇数，所以在循环的时候

i=1~(n+1)/2

也就是判了一下最中间那个保镖是否就站在被保护人的位置

见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct point{
    double x,y;
}a[20005];
int n;
bool cmp(point &x,point &y)
{
    if(x.y==y.y)return x.x<y.x;
    return x.y<y.y;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);
    point t;
    t.x=(a[1].x+a[n].x)/2.0;
    t.y=(a[1].y+a[n].y)/2.0;
    for(int i=1;i<=(n+1)/2;i++)
    {
        point tmp;
        tmp.x=(a[i].x+a[n-i+1].x)/2.0;
        tmp.y=(a[i].y+a[n-i+1].y)/2.0;
        if(t.x!=tmp.x||t.y!=tmp.y){
            printf("This is a dangerous situation.");
            return 0;
        }
    }
    printf("V.I.P. should stay at (%.1f,%.1f).",t.x,t.y);
    return 0;
}