这道题，先讲一下我的做题思路
这道题的最主要的目的就是算出中心，我下面称为中点。这个中点其实很好算的，我们只需要算出最左下角的坐标和最右上角的坐标，然后用中点坐标公式算出来就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;
}