Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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 (x_i,y_i), 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;
}