| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:历时3个小时……终于T T 用ttbobo大牛的数据过的,跪谢~~~~~~~~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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator