1551.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1551 on 2006-01-12 at 14:08:34 */ 
#include <cstdio>

const int MAX = 1024;

int x[MAX], y[MAX], n;

int carve(int, int);
bool through(int, int, int, int);
inline int code(int);

int main()
{
	int i, t;

	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		int sym = 0;
		for(i = 0; i < n; i++) scanf("%d %d", &x[i], &y[i]);
		for(i = 0; i < n; i++) 
			sym += carve(i, i+1)+carve(i, i+2);
		printf("Polygon #%d has %d symmetry line(s).\n", t, sym/2);
	}
	
	return 0;
}

int carve(int b, int e)
{
	bool ex = false;
	if(e - b == 2) ex = true;
	b = code(b); e = code(e);
	int cb = b, ce = e, m = (n+1)/2, i;
	if(ex && !through(b, e, code(b+1), code(e-1))) return 0;
	for(i = 0; i < m; cb = code(cb-1), ce = code(ce+1), i++)
		if(!through(b, e, cb, ce)) return 0;
	return 1;
}
bool through(int ls, int rs, int lt, int rt)
{
	int dsx = x[ls]-x[rs], dsy = y[ls]-y[rs];
	int dtx = x[lt]-x[rt], dty = y[lt]-y[rt];
	if(dsx*dty != dtx*dsy) return false;
	else {
		int dmx = x[ls]+x[rs]-x[lt]-x[rt], dmy = y[ls]+y[rs]-y[lt]-y[rt];
		return (dsx*dmx+dsy*dmy == 0);
	}
}
inline int code(int i)
{
	if(i >= n) return i-n;
	else if(i < 0) return i+n;
	else return i;
}