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

3
1 1
2 2
3 3

3
1 1
2 2
1 1

4
1 1
2 2
3 3
2 2

0

Sample Output

C

CC

Remove 1 bead(s), C

Source

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

       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;
}




全部评论

相关推荐

本神尊:看来是没招到小红薯上的人
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-24 14:18
点赞 评论 收藏
分享
06-20 21:22
已编辑
门头沟学院 Java
纯真的河老师在喝茶:答应了就跑啊,实习随便跑啊,别被pua了,md就是找个廉价劳动力,还平稳过度正式工,到时候跟你说没转正
点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务