[UVA] 10416 - Folding My T-Shirt
Problem F
Folding My T-Shirt
Input: standard input
Output: standard output
Time Limit: 2 seconds
Memory Limit: 16 MB
I have a T-Shirt. When I don't wear it any more, I fold it up. For most of the time, I can find a line so that the parts of the T-shirt on both sides are symmetrical. Then, I can fold it along that line. But sadly, I cannot find such a line for some strange(really really strange, see sample input ^_^) T-shirts.
In the example above, I can fold the T-shirt along the dash line, then, I got the figure on the right. Could you tell me if I can succeed?
Input
The first line of the input contains a single integer t(t<=20) indicating the number of test cases. Each test case begins with a line containing a single integer n(3<=n<=100) indicating the number of points of the polygon. In the next n lines each contain a pair of integers (xi,yi), indicating the position of the points. The points are given in the counter-clockwise order. The T-Shirt is valid. i.e not self-crossing. But the T-Shirt maybe not convex.
Output
For each test case, output a line corresponding the answer. Answer 'Yes' if the T-Shirt can be folded, 'No' otherwise.
Sample Input
2
3
0 0
5 0
1 1
8
1 0
2 0
2 1
-2 1
-2 0
-1 0
-1 -3
1 -3
Sample Output
No
Yes
The 2nd OIBH Online Programming Contest. Author: Rujia Liu
題目描述：
給一個簡單多邊形，問能不能使用一條線使之對稱。
題目解法：
1) 當點數 n 為奇數時
窮舉 i-th 點和 (i+(n-1)/2)-th 與(i+(n-1)/2)-th 的中點拉線，
查看是否為對稱關係。
2) 當點數 n 為偶數時
2.1 窮舉 i-th 點和 (i+n/2)-th 點拉線，查看是否為對稱關係。
2.2 窮舉 i-th 點與 (i+1)-th 點的中點 和 (i+n/2)-th 點與 (i+n/2+1)-th 點的中點拉線，查看是否為對稱關係。
計算時特別小心浮點數誤差，經過實驗後，用 double 計算時產生一堆 WA。
先將所有點的值都乘上 2，因此在取中點時不會有浮點數問題，而在檢查能不能左右對稱時，採用從線的兩側同時檢查，查看中點也在線上，且線的法向量與拉出向量外積 = 0
#include <stdio.h>
#include <math.h>
#include <set>
#include <algorithm>
using namespace std;
int n, x[105], y[105];
int main() {
int testcase;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d %d", &x[i], &y[i]);
x[i] *= 2;
y[i] *= 2;
}
int ret = 0;
if(n < 3) ret = 1;
if(n&1) {// odd
int idx = n/2;
for(i = 0; i < n; i++) {
int mx, my;
int a, b, c;
mx = (x[(i+idx)%n]+x[(i+idx+1)%n])/2;
my = (y[(i+idx)%n]+y[(i+idx+1)%n])/2;
a = my - y[i];
b = x[i] - mx;
c = - (a*x[i] + b*y[i]);
int flag = 1;
for(j = 0; j < n; j++) {
int ax = x[(i+1+j)%n];
int ay = y[(i+1+j)%n];
int bx = x[(i-1-j+n+n)%n];
int by = y[(i-1-j+n+n)%n];
mx = (ax+bx)/2;
my = (ay+by)/2;
if(a*mx + b*my + c != 0 || (ax-bx)*b != (ay-by)*a)
flag = 0;
}
if(flag) {
ret = 1;
break;
}
}
} else {
int idx = n/2;
for(i = 0; i < n; i++) {
int mx, my, a, b, c;
a = y[(i+idx)%n] - y[i];
b = x[i] - x[(i+idx)%n];
c = - (a*x[i] + b*y[i]);
int flag = 1;
for(j = 0; j < n; j++) {
int ax = x[(i+1+j)%n];
int ay = y[(i+1+j)%n];
int bx = x[(i-1-j+n+n)%n];
int by = y[(i-1-j+n+n)%n];
mx = (ax+bx)/2;
my = (ay+by)/2;
if(a*mx + b*my + c != 0 || (ax-bx)*b != (ay-by)*a)
flag = 0;
}
if(flag) {
ret = 1;
break;
}
}
for(i = 0; i < n; i++) {
int mx1, my1, mx2, my2;
int a, b, c;
mx1 = (x[i] + x[(i+1)%n])/2;
my1 = (y[i] + y[(i+1)%n])/2;
mx2 = (x[(i+idx)%n] + x[(i+idx+1)%n])/2;
my2 = (y[(i+idx)%n] + y[(i+idx+1)%n])/2;
a = my2 - my1;
b = mx1 - mx2;
c = - (a*mx1 + b*my1);
int flag = 1, mx, my;
for(j = 0; j < n; j++) {
int ax = x[(i+1+j)%n];
int ay = y[(i+1+j)%n];
int bx = x[(i-j+n+n)%n];
int by = y[(i-j+n+n)%n];
mx = (ax+bx)/2;
my = (ay+by)/2;
if(a*mx + b*my + c != 0 || (ax-bx)*b != (ay-by)*a)
flag = 0;
}
if(flag) {
ret = 1;
break;
}
}
}
puts(ret ? "Yes" : "No");
}
return 0;
}