sdnu 1137 Clockwise 关于平面几何的运用~~啥子

1137.Clockwise

Time Limit: 1000 MS Memory Limit: 32768 KB
Total Submission(s): 8 Accepted Submission(s): 2

Description

Saya have a long necklace with N beads, and she signs the beads from 1 to N. Then she fixes them to the wall to show N-1 vectors – vector i starts from bead i and end up with bead i+1.
One day, Kudo comes to Saya’s home, and she sees the beads on the wall. Kudo says it is not beautiful, and let Saya make it better.
She says: “I think it will be better if it is clockwise rotation. It means that to any vector i (i<n-1), t="" 0≤t<180.”
It is hard for Saya to reset the beads’ places, so she can only remove some beads. To saving the beads, although she agrees with Kudo’s suggestion, she thinks counterclockwise rotation is also acceptable. A counterclockwise rotation means to any vector i (i<n-1), t="" while="" degrees,="" rotate="" after="" i+1="" vector="" with="" direction="" same="" the="" have="" will="" it="" 0<t≤180.”
Saya starts to compute at least how many beads she should remove to make a clockwise rotation or a counterclockwise rotation.
Since the necklace is very-very long, can you help her to solve this problem?

Input

The input consists of several test cases.
The first line of input in each test case contains one integer N (2<n≤300), the="" beads.
Each of the next N lines contains two integer x and y, represents the coordinate of the beads. You can assume that 0<x, y<10000.
The last case is followed by a line containing one zero.

Output

For each case, print your answer with the following format:
If it is clockwise rotation without removing any beads, please print “C; otherwise if it is counterclockwise rotation without removing any beads, print “CC” instead; otherwise, suppose remove at least x beads to make a clockwise rotation and remove at least y beads to make a counterclockwise rotation. If x≤y, print “Remove x bead(s), C”, otherwise print “Remove x bead(s), CC” instead.
Your output format should imitate the sample output. Print a blank line after each test case.

Sample Input

Sample Output

C

CC

Remove 1 bead(s), C

Source

山东省ACM 2010年第一届省赛

做这道题之前，我们要先明白一些关于平面几何的运用；

1.关于点积：两点之间的点积a·b=|a||b|cosβ；得出来的结果可看成一个向量在另一个向量上的投影；如果是正数则表示两个向量指向的方向大致相同（相差不大于90）。公式一般是a.x*b.x+a.y+b.y;

2.关于叉积：两点之间的叉积a*b:得出来的结果在二维上可看成两向量围成的三角形面积的两倍；也可通过他的正负来判断两向量的左右位置关系：比如a.x*b.y-a.y*b.x>0,就表示a在b的右边，也就是顺时针方向；

3.这道题需要用dp来做；dp[a][b]表示以ab这个向量为终点的的图形包含有几个向量元素。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define ling 1e-10//0.00000000001
int dp[1100][1100];
struct point
{
	double x, y;
	point(double x = 0, double y = 0) :x(x), y(y) {}
};
point p[1100];
typedef point vectors;
vectors operator - (point a, point b)
{
	return vectors(a.x - b.x, a.y - b.y);
}
double cross(vectors a, vectors b)
{
	return (a.x*b.y - b.x*a.y);
}
double dot(vectors a, vectors b)
{
	return a.x*b.x + a.y*b.y;
}
bool check(int i, int j, int k)
{
//	cout << p[i].x << p[i].y << " " << p[j].x << p[j].y <<" "<<p[k].x<<p[k].y<< endl;
	vectors v1 = p[i] - p[j];
	vectors v2 = p[j] - p[k];
//	cout << v1.x << v1.x << " " << v2.x << v2.y << endl; 
	double a = cross(v1, v2);
	if (fabs(a) < ling)
	{
	//	cout << dot(v1, v2)<<"  "<<cross(v1,v2)<< endl;
		if ((dot(v1, v2) > ling))
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}
	else if (a > ling)
	{
		return 1;
	}
	return 0;
}
int main()
{
	int n;
	while (cin >> n&&n)
	{
		for (int s = 0; s < n; s++)
		{
			cin >> p[s].x >> p[s].y;
		}
		memset(dp, 0, sizeof(dp));
		int sm = -9;
		for (int a = 2; a < n; a++)
		{
			for (int b = 1; b < a; b++)
			{
				for (int c = 0; c < b; c++)
				{
					if (check(a, b, c))
					{
						if (dp[a][b] < dp[b][c] + 1)
						{
							dp[a][b] = dp[b][c] + 1;
						}
					}
				}
				if (dp[a][b] > sm)
				{
					sm = dp[a][b];
				}
			}
		}
		memset(dp, 0, sizeof(dp));
	//	cout << sm << endl;
		int sn = -1;
		for (int a = 2; a < n; a++)
		{
	//		cout << "asdasd" << endl;
			for (int b = 1; b < a; b++)
			{
				for (int c = 0; c < b; c++)
				{
					if (!check(a, b, c))
					{
						if (dp[a][b] < dp[b][c] + 1)
						{
							dp[a][b] = dp[b][c] + 1;
						}
					}
				}
				if (dp[a][b] > sn)
				{
					sn = dp[a][b];
				}
			}
		}
	//	cout << sn << endl;
	//	cout << sm << " " << sn << endl;
		int bz = n - 2;
		if (sm == bz)
		{
			cout << "C" << endl;
		}
		else if (sn == bz)
		{
			cout << "CC" << endl;
		}
		else if (sm >= sn)
		{
			printf("Remove %d bead(s), C\n", bz - sm);
		}
		else
		{
			printf("Remove %d bead(s), CC\n", bz - sn);
		}
		cout << endl;
	}
	return 0;
}