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:调了随机的次数+RP高点 0MS

Posted by 1001lisite at 2012-03-27 20:50:13 on Problem 2420
In 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:
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