hdu-5721 Palace(最近点对)
题目链接:
Palace
Time Limit: 8000/4000 MS (Java/Others)
Memory Limit: 262144/262144 K (Java/Others)
There are n palaces in the underworld, which can be located on a 2-Dimension plane with (x,y) coordinates (where x,y are integers). Psyche would like to find the distance of the closest pair of two palaces. It is the password to enter the main palace.
However, the underworld is mysterious and changes all the time. At different times, exactly one of the n palaces disappears.
Psyche wonders what the distance of the closest pair of two palaces is after some palace has disappeared.
Print the sum of the distance after every single palace has disappeared.
To avoid floating point error, define the distance d between palace (x1,y1) and (x2,y2) as d=(x1−x2)2+(y1−y2)2.
For each testcase, the first line contains an integers n (3≤n≤105), which denotes the number of temples in this testcase.
The following n lines contains n pairs of integers, the i-th pair (x,y) (−105≤x,y≤105) denotes the position of the i-th palace.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss)); typedef long long LL; template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
if(!p) { puts("0"); return; }
while(p) stk[++ tp] = p%10, p/=10;
while(tp) putchar(stk[tp--] + '0');
putchar('\n');
} const LL mod=998244353;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=1e5+10;
const int maxn=1e3+10;
const double eps=1e-6; struct node
{
LL x,y;
}po[N],temp[N],po1[N];
int cmp1(node a,node b)
{
return a.x<b.x;
}
int cmp2(node a,node b)
{
return a.y<b.y;
}
node fa,fb;
LL ans;
LL get_dis(node a, node b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
LL merge(int l,int r)
{
if(r-l<=1)
{
if(l==r)return inf;
else
{
LL dis=get_dis(po[l],po[r]);
if(dis<ans)
{
fa=po[l];
fb=po[r];
ans=dis;
}
return dis;
}
} int mid=(l+r)>>1;
LL dl=merge(l,mid),dr=merge(mid+1,r),d=min(dl,dr);
int cnt=0;
For(i,l,r)
{
if(abs(po[mid].x-po[i].x)<=d)temp[++cnt]=po[i];
}
sort(temp+1,temp+cnt+1,cmp2);
For(i,1,cnt)
{
for(int j=i+1;j<=cnt&&temp[j].y-temp[i].y<d;j++)
{
LL dis=get_dis(temp[j],temp[i]);
if(dis<d)d=dis;
if(dis<ans)
{
ans=dis;
fa=temp[j];
fb=temp[i];
}
}
}
return d;
} LL work(int l,int r)
{
ans=inf;
sort(po+l,po+r+1,cmp1);
return merge(l,r);
}
int main()
{
int t;
read(t);
while(t--)
{
int n;
read(n);
For(i,1,n)read(po1[i].x),read(po1[i].y),po[i]=po1[i]; LL sum=0;
sum+=work(1,n)*(LL)(n-2);
node faa=fa,fbb=fb;
int flag=0;
For(i,1,n)
{
if(po1[i].x==faa.x&&po1[i].y==faa.y&&flag==0)
{
flag=1;
po[i].x=1e7;
po[i].y=1e7;
continue;
}
po[i]=po1[i];
}
sum+=work(1,n);
flag=0;
For(i,1,n)
{
if(po1[i].x==fbb.x&&po1[i].y==fbb.y&&flag==0)
{
flag=1;
po[i].x=1e7;
po[i].y=1e7;
continue;
}
po[i]=po1[i];
}
sum+=work(1,n);
cout<<sum<<"\n";
} return 0;
}
最新文章
- 修改LR自带的示例程序端口号
- ups机制下停电提前关闭oracle数据库
- Linux共享库 日志方法
- 百度之星复赛 1004 / hdu5715 二分dp+trie
- JS中javascript:void(0)真正含义
- C#面向对象(二)
- Java做acm所需要的基础知识之排序问题
- HttpClient 请求WebApi
- URAL 1303
- 框架原理第一讲,熟悉常用的设计方式.(以MFC框架讲解)
- Html5+js测试题(开发版)
- 面向面试题和实际使用谈promise
- js 滚轮控制图片缩放大小和拖动
- 基于ROS的运动识别
- SqlServer数据库链接字符串
- Android MVP 架构一 View与Presenter
- Redis Cluster高可用集群在线迁移操作记录【转】
- Geolocation API
- 在JavaScript文件中用ajax方法实现省市区的三级联动
- Android webview背景设置为透明无效 拖动时背景闪烁黑色