枚举 – edward

【题目大意】
给定n个点，求每个点到离他最近点的距离。
【算法分析】
V图什么的，最讨厌了。。。
我直接就暴力了。。。
按x把点排序，然后按j递增序，枚举i-j的点和i+j的点。如果(a[i].x-a[i-j].x)^2 > dis && (a[i].x-a[i+j].x)^2 > dis
那么就break吧。
复杂度还是n^2的。
其中dis为之前枚举所得的较优解。
【其它】果断排到超级后面。
叉姐说，见到题目要先水一水，水不过再切。。。= =
【CODE】
#include #include #include #include #define dis(A,B) ( (lld)(A.x-B.x)*(lld)(A.x-B.x) + (lld)(A.y-B.y)*(lld)(A.y-B.y) )
#define Sqr(x) ((lld)(x)*(lld)(x))
using namespace std;
typedef long long lld;
const lld INF=(lld)(2000000000)*(lld)(2000000000);
int Tc;
int n;
struct Point{int x,y,pos; lld dis;}a[105555];

bool cmp(Point A,Point B){
return A.x}

void init(){
scanf("%d",&n);
int i;
for (i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
a[i].pos=i;
}
sort(a+1,a+n+1,cmp);
}

void work(){
int i,j;
bool flag;
lld tmp;
for (i=1;i<=n;i++){
a[i].dis=INF;
for (j=1;(i-j>=1 || i+j<=n);j++){
flag=false;
if (i-j>=1 && Sqr(a[i].x-a[i-j].x) tmp=dis(a[i],a[i-j]);
if (tmp flag=true;
}
if (i+j<=n && Sqr(a[i+j].x-a[i].x) tmp=dis(a[i],a[i+j]);
if (tmp flag=true;
}
if (!flag) break;
}
}
}

bool cmp2(Point A,Point B){
return A.pos}

void output(){
sort(a+1,a+n+1,cmp2);
for (int i=1;i<=n;i++)
printf("%I64dn",a[i].dis);
}

int main(){
scanf("%d",&Tc);
for (int i=0;i init();
work();
output();
}
}

标签存档：枚举

[HDOJ2966 In case of failure]【平面每个点的最近点对】【暴力T_T】

[SGU108 Self-numbers 2]【枚举】【常数题】