[COGS2426][HZOI 2016]幾何

題目大意：

給定平面坐標系內\(n\)個整點，求這些整點能構成的正多邊形的邊數的最大值。

思路：

一個基本結論：平面直角坐標系內能夠形成的正多邊形一定是正方形。

因此枚舉兩個點就可以推出另外兩個點，判斷這兩個點是否在給定的點集中即可。

時間復雜度\(\mathcal O(n^2\log n)\)。

源代碼：

#include<set> #include<cstdio> #include<cctype> inline int getint() {register char ch;register bool neg=false;while(!isdigit(ch=getchar())) neg=ch=='-';register int x=ch^'0';while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');return neg?-x:x; } const int N=1001; struct Point {int x,y;bool operator < (const Point &rhs) const {return x==rhs.x?y<rhs.y:x<rhs.x;} }; Point p[N]; std::set<Point> set; int main() {freopen("geometry.in","r",stdin);freopen("geometry.out","w",stdout);for(register int T=getint();T;T--) {const int n=getint();for(register int i=1;i<=n;i++) {p[i].x=getint();p[i].y=getint();set.insert(p[i]);}for(register int i=1;i<=n;i++) {const Point &a=p[i];for(register int j=1;j<=n;j++) {if(i==j) continue;const Point &b=p[j];const int d1=a.y-b.y,d2=b.x-a.x;const Point &c=(Point){a.x+d1,a.y+d2};const Point &d=(Point){b.x+d1,b.y+d2};if(set.count(c)&&set.count(d)) {puts("4");goto Next;}}}puts("-1");Next:;set.clear();}return 0; }

轉載于:https://www.cnblogs.com/skylee03/p/9361978.html

總結

以上是生活随笔為你收集整理的[COGS2426][HZOI 2016]几何的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。