| ||||||||||
| 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 | |||||||||
我的为什么老WA? 好心人看看。我剪枝了一下, 难道是这问题?/*
* poj 2236 彻底的自己编一个UFS看?
*/
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1008
//#define K 300008
struct _node{
int dx;
int dy;
}node[N];
int rank[N]={0}, p[N], visit[N] = {0};
int find( int x ) {
if( x==p[x] )
return p[x];
else
return find( p[x] );
}
void merge( int root1, int root2 ) {
int x=find( root1 );
int y=find( root2 );
if( x==y )
return ;
if( rank[x]>rank[y] )
p[y] = x;
else{
p[x] = y;
if( rank[x]==rank[y] )
rank[y]++;
}
}
bool cmp( const _node a, const _node b ) {
if( a.dx != b.dx )
return a.dx<b.dx;
else
return a.dy<b.dy;
}
int main() {
//freopen( "c:\\in.txt" , "r", stdin );
//freopen( "c:\\out.txt" , "w", stdout );
double temp1, temp2, temp3, temp4, tmp;
int n, d;
int i, j, k;
int x, y, z;
char c;
scanf( "%d %d", &n, &d );
for( i=1; i<=n; i++ )
p[i] = i;
for( i=1; i<=n; i++ ) {
scanf( "%d %d", &node[i].dx, &node[i].dy );
}
sort( &node[1], &node[n]+1, cmp );
getchar(); //
while( scanf( "%c", &c )!=EOF ) {
if( c=='O' ) {
scanf( "%d", &z );
getchar();//
visit[z] = 1;
k=node[z].dx-d; //这个地方开始有问题!!!
if( k<0 )
i=1;
else {
for( i=z; i>0; i-- ) {
if( node[i].dx<k )
break;
}
}
for( ; node[i].dx<=(z+d); i++ ) {
if( visit[i] ) {
temp1=( node[i].dx - node[z].dx );
temp2=( node[i].dy - node[z].dy );
temp3 = temp1*temp1;
temp4 = temp2*temp2;
tmp = temp3 + temp4;
if( tmp<=d ) {
merge( i, z );
}
}
}
}
else if( c=='S' ) {
scanf( "%d %d", &x, &y );
getchar();
if( find(x) == find(y) )
printf( "SUCCESS\n" );
else
printf( "FAIL\n" );
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator