Red Huang

Red Huang

uva 10575

Add the midpoint between each pair of points as a vertex.

Enumerate each point on the axis of symmetry one by one, and calculate the vector of the axis of symmetry.

Then, the vector between all pairs of points must be perpendicular to the vector of the axis of symmetry.

And the midpoint between each pair of points must be parallel to the vector of the axis of symmetry.

Only when all of these conditions are met, it is considered an axis of symmetry.

Because of the symmetry relationship, it will be repeated once, so remember to divide by 2.

//  
//        GGGGGGGGGGGGG        CCCCCCCCCCCCC               AAA  
//     GGG::::::::::::G     CCC::::::::::::C              A:::A  
//   GG:::::::::::::::G   CC:::::::::::::::C             A:::::A  
//  G:::::GGGGGGGG::::G  C:::::CCCCCCCC::::C            A:::::::A  
// G:::::G       GGGGGG C:::::C       CCCCCC           A:::::::::A  
//G:::::G              C:::::C                        A:::::A:::::A  
//G:::::G              C:::::C                       A:::::A A:::::A  
//G:::::G    GGGGGGGGGGC:::::C                      A:::::A   A:::::A  
//G:::::G    G::::::::GC:::::C                     A:::::A     A:::::A  
//G:::::G    GGGGG::::GC:::::C                    A:::::AAAAAAAAA:::::A  
//G:::::G        G::::GC:::::C                   A:::::::::::::::::::::A  
// G:::::G       G::::G C:::::C       CCCCCC    A:::::AAAAAAAAAAAAA:::::A  
//  G:::::GGGGGGGG::::G  C:::::CCCCCCCC::::C   A:::::A             A:::::A  
//   GG:::::::::::::::G   CC:::::::::::::::C  A:::::A               A:::::A  
//     GGG::::::GGG:::G     CCC::::::::::::C A:::::A                 A:::::A  
//        GGGGGG   GGGG        CCCCCCCCCCCCCAAAAAAA                   AAAAAAA  
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <cmath>  
#include <climits>  
#include <vector>  
#include <set>  
#include <map>  
#include <queue>  
#include <cctype>  
#include <utility>  
#include <ctime>  
#include <complex>  
using namespace std;  
#ifdef DEBUG  
#define VAR(a,b) decltype(b) a=(b)  
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)  
#define gettime() end\_time=clock();printf("now running time is %.7f\\n",(float)(end\_time - start\_time)/CLOCKS\_PER\_SEC);  
#else  
#define VAR(a,b) \_\_typeof(b) a=(b)  
#define debug(...)  
#define gettime()  
#endif  
typedef unsigned int uint;  
typedef long long int Int;  
typedef unsigned long long int UInt;  
#define Set(a,s) memset(a,s,sizeof(a))  
#define Write(w) freopen(w,"w",stdout)  
#define Read(r) freopen(r,"r",stdin)  
#define Pln() printf("\\n")  
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()  
#define De(x)printf(#x"%d\\n",x)  
#define For(i,x)for(int i=0;i<x;i++)  
#define CON(x,y) x##y  
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\  
    printf("%d ",dp\[htx\]\[hty\]);}Pln();}  
#define M 2005  
#define PII pair<int,int\>  
#define PB push\_back  
#define oo INT\_MAX  
#define Set\_oo 0x3f  
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)  
#define eps 1e-6  
#define X first  
#define Y second  
clock\_t start\_time=clock(), end\_time;  
bool xdy(double x,double y){return x>y+eps;}  
bool xddy(double x,double y){return x>y-eps;}  
bool xcy(double x,double y){return x<y-eps;}  
bool xcdy(double x,double y){return x<y+eps;}  
int min3(int x,int y,int z){  
    int tmp=min(x,y);  
    return min(tmp,z);  
}  
int max3(int x,int y,int z){  
    int tmp=max(x,y);  
    return max(tmp,z);  
}  
#define x real()  
#define y imag()  
typedef complex<int\> pt;  
int n;  
pt p\[M\];  
int dot(pt a,pt oa,pt b,pt ob){  
    return (a.x-oa.x)\*(b.x-ob.x)+(a.y-oa.y)\*(b.y-ob.y);  
}  
int cross(pt o,pt a,pt b){  
    return (a.x-o.x)\*(b.y-o.y)-(b.x-o.x)\*(a.y-o.y);  
}  
int ff=0;  
void solve(){  
    int ans=0;  
    for(int i=0;i<n;i++){  
        int pi=(i-1+n)%n,ni=(i+1)%n;  
        pt cm=(p\[pi\]+p\[ni\])/2;  
        if(cm==p\[i\]){  
            cm=pt(p\[i\].x+p\[i\].y-p\[ni\].y,p\[i\].y-p\[i\].x+p\[ni\].x);  
        }  
        int j;  
        for(j=1;j<n/2;j++){  
            int pi=(i-j+n)%n,ni=(i+j)%n;  
            pt cm2=(p\[pi\]+p\[ni\])/2;  
//        debug("%d %d\\n",cm2.x,cm2.y);  
            if(dot(cm,p\[i\],p\[pi\],p\[ni\])!=0){  
                break;  
            }  
            else if(cross(cm,cm2,p\[i\])!=0)  
                break;  
        }  
        if(j==n/2){  
            if(cross(cm,p\[i\],p\[(i+n/2)%n\])==0){  
                ans++;  
//                debug("%d\\n",i);  
            }  
        }  
    }  
    printf("Polygon #%d has %d symmetry line(s).\\n",++ff,ans/2);  
}  
int main() {  
    ios\_base::sync\_with\_stdio(0);  
    while(~scanf("%d",&n)&&n){  
        n\*=2;  
        for(int i=0;i<n;i+=2){  
            int a,b;  
            scanf("%d %d",&a,&b);  
            p\[i\]=pt(a,b);  
            p\[i\]=4\*p\[i\];  
        }  
        for(int i=1;i<n;i+=2){  
            int pi=(i-1+n)%n,ni=(i+1)%n;  
            p\[i\]=(p\[pi\]+p\[ni\])/2;  
        }  
        solve();  
    }  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
}  

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.