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