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:调了随机的次数+RP高点 0MSIn Reply To:orz……被神犇们集体鄙视了……话说用小号试各种参数刷了n次,最快刷到32ms,就是刷不到0ms……看来我还是太弱了T__T Posted by:xuhaoran510 at 2011-06-29 22:55:05 //Name: Eme丶 #include<cstring> #include<cstdio> #include<cstdlib> #include<iostream> #include<cmath> using namespace std; struct zuobiao { double x,y,dis; }; int n; double ans,maxx,maxy; zuobiao map[110],a[20]; double get(double x,double y) { double length=0; for (int i=1;i<=n;i++) length+=sqrt((map[i].x-x)*(map[i].x-x)+(map[i].y-y)*(map[i].y-y)); return length; } int main() { srand(time(NULL)); scanf("%d",&n); maxx=-1e5; maxy=-1e5; for (int i=1;i<=n;i++) { scanf("%lf%lf",&map[i].x,&map[i].y); if (map[i].x>maxx) maxx=map[i].x; if (map[i].y>maxy) maxy=map[i].y; } for (int i=1;i<=20;i++) { a[i].x=rand()%(int)maxx+1; a[i].y=rand()%(int)maxy+1; a[i].dis=get(a[i].x,a[i].y); } for (int i=1;i<=1000;i++) for (int j=1;j<=20;j++) for (int k=1;k<=5;k++) { zuobiao temp; temp.x=(rand()%1000+1)*0.001; temp.y=(rand()%1000+1)*0.001; double dis; for (int now1=-1;now1<=1;now1+=2) for (int now2=-1;now2<=1;now2+=2) { dis=get( (temp.x*now1)+a[j].x , (temp.y*now2)+a[j].y ); if (dis<a[j].dis) { a[j].x=temp.x*now1+a[j].x; a[j].y=temp.y*now2+a[j].y; a[j].dis=dis; } } } ans=1e8; for (int i=1;i<=20;i++) if (a[i].dis<ans) ans=a[i].dis; printf("%.0lf\n",ans); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator