Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:历时3个小时……终于T T 用ttbobo大牛的数据过的,跪谢~~~~~~~~

Posted by Web_Board at 2009-10-06 01:01:45 on Problem 1113
In Reply To:历时3个小时……终于T T Posted by:Web_Board at 2009-10-06 00:59:43
> #include<stdio.h>
> #include<math.h>
> 
> int main()
> {
> 	freopen("in.txt","r",stdin);
> 	double result = 0.0;
> 	int stack[1001] = {0};
> 	int ptr = 0;
> 	int point[1001][2];
> 	bool In_Circle[1001] = {false};
> 	int R,n,nextp = 0,now;
> 	int maxy = 100000,my = 0;
> 	scanf("%d %d",&n,&R);
> 	for(int i = 1;i <= n;i ++)
> 	{
> 		scanf("%d %d",&point[i][0],&point[i][1]);
> 		if(point[i][1] < maxy)
> 		{
> 			my = i;
> 			maxy = point[i][1];
> 		}
> 	}
> 	double rad[1001] = {0.0};
> 	int prev[2] = {1,0};
> 	int nowv[2];
> 	now = my;//start from my
> 	stack[0] = my;
> 	do
> 	{
> 		double maxr = -2.0;
> 		int maxrp = now;
> 		for(int i = 1;i <= n;i ++)
> 		{
> 			if(!In_Circle[i] && i != now)
> 			{
> 				nowv[0] = point[i][0] - point[now][0];
> 				nowv[1] = point[i][1] - point[now][1];
> 				double dy = (double)((nowv[0]) * (prev[0]) + (nowv[1] * prev[1]));
> 				double len = (double)(nowv[0] * nowv[0] + nowv[1] * nowv[1]) * (prev[0] * prev[0] + prev[1] * prev[1]);
> 				rad[i] = (dy / sqrt(len));
> 				if(maxr < rad[i])
> 				{
> 					maxr = rad[i];
> 					maxrp = i;
> 				}
> 			}
> 		}
> 		stack[++ptr] = maxrp;
> 		In_Circle[maxrp] = true;
> 		prev[0] = point[maxrp][0] - point[now][0];
> 		prev[1] = point[maxrp][1] - point[now][1];
> 		now = maxrp;
> 	}while(now != my);
> 
> 	result += R * acos(prev[0] * 1.0 / sqrt((double)(prev[0] * prev[0] + prev[1] * prev[1])));
> 
> 	while(ptr)
> 	{
> 		result += acos(rad[stack[ptr]]) * R;
> 		result += sqrt((double)((point[stack[ptr]][0] - point[stack[ptr - 1]][0]) * (point[stack[ptr]][0] - point[stack[ptr - 1]][0]) + 
> 							(point[stack[ptr]][1] - point[stack[ptr - 1]][1]) * (point[stack[ptr]][1] - point[stack[ptr - 1]][1])));
> 		ptr --;
> 	}
> 	printf("%.0lf",result);
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator