b604 - Center of Symmetry
題目描述
題目給定一組平面上的點，要求判斷這組點是否存在一個對稱中心。如果存在一個點 s (不一定在點集合中)，使得對於集合中的每個點 p，都存在一個點 q 在集合中，滿足 p - s = s - q，則該點集合具有對稱中心。
解題思路
解題思路是首先計算所有點的平均座標，作為可能的對稱中心。然後，將點按照 x 座標和 y 座標排序。接著，對於每個點 p，檢查是否存在一個點 q，使得 p 和 q 相對於平均座標對稱。具體來說，檢查 p 的 x 座標減去平均座標的 x 座標是否等於平均座標的 x 座標減去 q 的 x 座標，並且 p 的 y 座標減去平均座標的 y 座標是否等於平均座標的 y 座標減去 q 的 y 座標。如果對於所有點都能找到滿足條件的點，則存在對稱中心，輸出 "yes"，否則輸出 "no"。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct pt{
int x,y;
};
bool cmp(pt xx,pt yy){
if(xx.x>yy.x||(xx.x==yy.x&&xx.y>yy.y))return 1;
return 0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
while(cin >> n){
if(n==0)break;
pt a[n];
int xa=0,ya=0,s=1;
for(int i=0;i<n;++i){
cin >> a[i].x >> a[i].y;
a[i].x*=2;
a[i].y*=2;
xa+=a[i].x;
ya+=a[i].y;
}
xa/=n;
ya/=n;
sort(a,a+n,cmp);
for(int i=0;i<n&&s;++i){
if(a[i].x-xa!=xa-a[n-i-1].x||a[i].y-ya!=ya-a[n-i-1].y){
s=0;
}
}
if(s){
cout << "yes\n";
}
else{
cout << "no\n";
}
}
}