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