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

这题居然能暴力!!!4000ms啊。。。一点没优化都过了

Posted by xx315 at 2015-06-16 19:34:19 on Problem 2236
#include<stdio.h>
#include<string.h>
using namespace std;
int pre[1005];
int n,d;
void init(){
    for(int i=1;i<=n;i++)
        pre[i]=i;
}
int find(int x){
    while(x!=pre[x])
        x=pre[x];
    return x;
}
struct node { int x,y,id,vis;}a[1010];

bool dis(int i,int j)
{
    if(((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))>d*d)
        return false;
    else return true;

}

int main(){

        scanf("%d%d",&n,&d);
        init();
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a[i].x,&a[i].y);
            a[i].id=i;
            a[i].vis=0;
        }
        char s[5];
        int v,u;
        while(scanf("%s",&s)!=EOF){
         if(s[0]=='S'){
            scanf("%d%d",&v,&u);
            int dx=find(v);
            int dy=find(u);
            if(pre[dx]!=pre[dy])
                printf("FAIL\n");
            else printf("SUCCESS\n");
         }
         if(s[0]=='O'){
            scanf("%d",&v);
            a[v].vis=1;
            int dx=find(v);
            for(int i=1;i<=n;i++){
             if(a[i].vis&&dis(v,i)&&v!=i){
              int dy=find(i);
              if(dx!=dy){
                pre[dy]=dx;
              }
             }
            }
         }

        }

return 0;
}

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