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