| 记录编号 |
238914 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
最小距离和 |
最终得分 |
100 |
| 用户昵称 |
 Satoshi |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
26.268 s |
| 提交时间 |
2016-03-19 15:26:11 |
内存使用 |
0.72 MiB |
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
#include <stack>
#include <time.h>
#define N 10010
using namespace std;
typedef long double ld;
ifstream in("space.in");
ofstream out("space.out");
int n,top;
ld ans=0,INF=ld(1<<28),Tans;
ld R=100,pi=acos(-1.0);
bool l[N]={0};
int fft[N]={0};//存储离模拟退火直线最近的100个点
class point
{
public:
ld x,y;//横纵坐标
void make(ld a,ld b)
{
x=a;
y=b;
}
void print()
{
out<<x<<' '<<y<<endl;
}
}po[N],P[11];
class line//直线的两点式方程:点A,B构成过A,B的直线，记做(A,B)
{
public:
point A,B;
void make(point a,point b)
{
A=a;B=b;
}
}Orz,zrO,OOO;
class fuck//不要在意名字.......,name存的是原下标
{
public:
ld dis;
int name;
}AC[N];
bool operator <(fuck a,fuck b)
{
return a.dis<b.dis;
}
point operator +(point a,point b)
{
point c;
c.x=a.x+b.x;
c.y=a.y+b.y;
return c;
}
point operator -(point a,point b)
{
point c;
c.x=a.x-b.x;
c.y=a.y-b.y;
return c;
}
point operator *(point a,ld b)
{
a.x*=b;
a.y*=b;
return a;
}
point operator /(point a,ld b)
{
a.x/=b;
a.y/=b;
return a;
}
ld operator *(point a,point b){return a.x*b.x+a.y*b.y;}
ld operator ^(point a,point b){return a.x*b.y-a.y*b.x;}
ld len(point a){return sqrt(a*a);}
ld dis(point a,point b)
{
point c;
c=a-b;
return len(c);
}
void print(ld a,int b){out<<setprecision(b)<<std::fixed<<a<<endl;}
bool com(point a,point b)
{
if(a.y<b.y)return 1;
if(a.y==b.y)if(a.x<b.x)return 1;
return 0;
}
void read()
{
int i;
in>>n;
for(i=1;i<=n;i++)in>>po[i].x>>po[i].y;
}
ld getH(point a,point b,point c)//点c到两点式方程a,b的距离
{
ld area=0;
area=fabs((a-b)^(b-c));//底乘高=面积
return area/dis(a,b);
}
ld sumdis(point a,point b)//统计这个两点式方程对所有点的距离和
{
int i;
ld sum=0;
for(i=1;i<=n;i++)sum+=getH(a,b,po[i]);
return sum;
}
int random(int l,int r)//生成[l,r]的随机数
{
int s;
s=l+rand()%(r-l+1);
return s;
}
ld random_real(void){//生成一个[0,1]内的实数
return ((((rand()<<15)|rand())&0x3fffffff)+0.0)/(0x3fffffff+0.0);
}
ld luangao(point S,point T)//对平移量进行模拟退火,这是一个向量方程，由位置向量S和方向向量T构成
{
int i;
point NS,NT,O;
ld step,best=INF,dir;
ld temp,Te,p;
for(step=10000,Te=1000;step>=0.001;step/=2,Te/=2)//step为步长，Te为温度
{
O=S;
if(Te>1)Te=1;
for(dir=-1;dir<=1;dir+=2)//把直线向上平移还是向下平移
{
NS.make(S.x+step*dir,0);
NT=NS+T;//以位置向量NS，方向向量T，构建(NS,NT)为新的两点式方程
temp=sumdis(NS,NT);//计算距离
if(temp<best)//更优解直接更新
{
best=temp;
O=NS;
zrO.make(NS,NT);//存储直线
}
else//不太优的解以一定概率更新
{
p=exp((best-temp)/Te);//更新概率(p=e^(-delta/T))
if(random_real()<=p)
{
best=temp;
O=NS;
zrO.make(NS,NT);//存储直线
}
}
}
S=O;
}
return best;
}
void work()
{
int i,j,m=4,rep;
ld angle,angles,angleo,temp,step,dir,best,Te,p;
point S,T;
ans=best=INF;
angle=angles=angleo=0;
for(i=1;i<=m;i++)//生成初始位置向量
{
P[i].x=random(0,10000);
P[i].y=random(0,10000);
}
for(i=1;i<=m;i++)
{
angle=angles=angleo=random(0,360);//随机初始极角
best=INF;
for(step=100,Te=100000;step>=0.001;step/=2,Te/1.8)
{
angleo=angles;
if(Te>1)Te=1;
for(dir=-1;dir<=1;dir+=2)//顺时针还是逆时针旋转极角
{
angle=angles+step*dir*pi/180;//产生新极角
T.make(R*cos(angle),R*sin(angle));//R=100(可以调整)，把极角转化为直线的方向向量T=(Rcosa,Rsina)
temp=luangao(P[i],T);//位置向量P[i],方向向量T产生的两点式方程为(P[i],P[i]+T)
if(best>temp)//以下作用和上文相同
{
best=temp;
angleo=angle;
Orz=zrO;
}
else
{
p=exp((best-temp)/Te);
if(random_real()<=p)
{
best=temp;
angleo=angle;
Orz=zrO;
}
}
}
angles=angleo;
}
if(ans>best)
{
ans=best;
OOO=Orz;
}
}//OOO存储的是最优直线
Tans=ans;
for(i=1;i<=n;i++)//求出离这条直线最近的100个点
{
AC[i].dis=getH(OOO.A,OOO.B,po[i]);
AC[i].name=i;
}
sort(AC+1,AC+n+1);//排序
for(i=1;i*i*n<=1000000&&i<=n;i++)fft[++top]=AC[i].name;
}
void baoli()
{
int i,j,k;
ld temp=0;
point S,T;
ans=INF;
for(i=1;i<=top;i++)//再使用100^3的暴力
{
for(j=i+1;j<=top;j++)
{
temp=sumdis(po[fft[i]],po[fft[j]]);
if(ans>temp)ans=temp;
}
}
Tans=fmin(Tans,ans);
print(Tans,2);
}
int main()
{
int start,end;
start=clock();
srand(time(NULL));
read();
work();
baoli();
end=clock();
return 0;
}