syhd142 |
|
|||
日歷
統計
導航常用鏈接留言簿(2)隨筆檔案(23)文章分類(270)
文章檔案(122)我的豆瓣搜索最新評論
閱讀排行榜
評論排行榜 |
題意:給你n個點集合S,問你是否存在一個對稱點,每個點關于這個對稱點可以找到另外一個在集合S中的點。對稱點不能屬于集合S。 解法:對稱點如果存在必然是這個n個點的橫縱坐標的平均值,可以證明,然而這是一個必要條件,還需要對每個點進行判斷是否存在關于對稱點對稱的集合S中的點。 #include <stdio.h>
#define N 10005 struct Point { int x, y; Point() {}; Point(int _x, int _y) { x = _x, y = _y; } }p[N]; bool solve(Point &ave, int n) { if((ave.x % n) || (ave.y % n)) return 0; ave.x /= n, ave.y /= n; for(int i = 0; i < n; i++) { int x = 2 * ave.x - p[i].x; int y = 2 * ave.y - p[i].y; bool mk = 0; for(int j = 0; j < n; j++) { if(x == p[j].x && y == p[j].y) { mk = 1; break; } } if(!mk) return 0; } return 1; } int main() { int t, n; scanf("%d", &t); while(t--) { scanf("%d", &n); Point ave(0, 0); for(int i = 0; i < n; i++) { scanf("%d %d", &p[i].x, &p[i].y); ave.x += p[i].x, ave.y += p[i].y; } if((n == 1) || solve(ave, n)) puts("yes"); else puts("no"); } return 0; }
|
![]() |
|
Copyright © Fucker | Powered by: 博客園 模板提供:滬江博客 |