P1227 【[JSOI2008]完美的对称】
阅读原文时间:2023年07月10日阅读:1

这道题,先讲一下我的做题思路

这道题的最主要的目的就是算出中心,我下面称为中点。这个中点其实很好算的,我们只需要算出最左下角的坐标和最右上角的坐标,然后用中点坐标公式算出来就ok了,那么这道题就做完了一半

中点坐标公式:

\(x_{mid}=(x_{min}+x_{max})/2\)

\(y_{mid}=(y_{min}+y_{max})/2\)

那么剩下的一半就是如何就算无解的情况了,首先这个中点我们已经算出来了,如果有什么疑惑的可以自己手模一下

对于无解的情况,我们对于\((x_i,y_i)\),若此时中点为\((x_{mid},y_{mid})\),那么这个点关于中点的中心对称之后的点就是\((2*x_{mid}-x_i,2*y_{mid}-y_i)\)

这个时候对于这个中心对称之后的点,我们只需要\(O(n)\)扫一下就可以了

那么给出第一份程序

#include<bits/stdc++.h>
#define MAXN 50000
#define INF 100000
using namespace std;
double n;
struct node{
    double x,y;
}a[MAXN];
double minx=INF,miny=INF,maxx=-INF,maxy=-INF;
double sx,sy;
bool find(double x,double y){
    for(register int i=1;i<=n;i++){
        if(a[i].x==x&&a[i].y==y) return true; //O(n) 扫一下
    }
    return false;
}
bool check(){
    for(register int i=1;i<=n;i++){
        double x=a[i].x,y=a[i].y;
        if(find(2*sx-x,2*sy-y)==false) return false; //如果找不到中心对称之后的点,说明不行
    }
    return true;
}
int main(){
    scanf("%lf",&n);
    for(register int i=1;i<=n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
        minx=min(minx,a[i].x);
        miny=min(miny,a[i].y);
        maxx=max(maxx,a[i].x);
        maxy=max(maxy,a[i].y);
    }
    sx=(double)(maxx+minx)*1.0/2;
    sy=(double)(maxy+miny)*1.0/2;
    //算出中点
    if(check()==false){
        puts("This is a dangerous situation!");
    }else printf("V.I.P. should stay at (%.1f,%.1f).",sx,sy);
    return 0;
}

然后就会发现这个程序跑出来慢得离谱,我的是\(2.9s\),因为每一次查找确实需要用掉太多时间,那如何去优化这个时间呢

我们可以对于所有的坐标进行排序,以\(x\)为第一关键字,\(y\)为第二关键字,那么我们的\(check()\)函数只需要循环\(1\)~\((n+1)/2\),然后我们的\(find()\)函数只需要循环\(n\)~\((n+1)/2\),这是运用了中心对称的性质,这样优化之后的程序是\(600s+\)

#include<bits/stdc++.h>
#define MAXN 50000
#define INF 100000
using namespace std;
int n;
struct node{
    double x,y;
}a[MAXN];
double minx=INF,miny=INF,maxx=-INF,maxy=-INF;
double sx,sy;
bool cmp(node q,node w){
    if(q.x==w.x) return q.y<w.y;
    return q.x<w.x;
}
bool find(double x,double y){
    for(register int i=n;i>=(n-1)/2-1;i--){ //这里的-1是因为c++是向下取整,多算一位
        if(a[i].x==x&&a[i].y==y) return true;
    }
    return false;
}
bool check(){
    for(register int i=1;i<=(n+1)/2+1;i++){  //这里的+1和上面的理由一样
        double x=a[i].x,y=a[i].y;
        if(find(2*sx-x,2*sy-y)==false) return false;
    }
    return true;
}
int main(){
    scanf("%d",&n);
    for(register int i=1;i<=n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
        minx=min(minx,a[i].x);
        miny=min(miny,a[i].y);
        maxx=max(maxx,a[i].x);
        maxy=max(maxy,a[i].y);
    }
    sort(a+1,a+1+n,cmp);
    sx=(double)(maxx+minx)*1.0/2;
    sy=(double)(maxy+miny)*1.0/2;
    if(check()==false){
        puts("This is a dangerous situation!");
    }else printf("V.I.P. should stay at (%.1f,%.1f).",sx,sy);
    return 0;
}