Poj Solution 2236

http://poj.org/problem?id=2236

//* @author: 82638882@163.com
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int a=in.nextInt();
  int max=in.nextInt();
  max*=max;
  int[] ax=new int[a+1];
  int[] ay=new int[a+1];
  int[] arr=new int[a+1];
  int[] bool=new int[a+1];
  for(int i=1;i<=a;i++)
    arr[i]=i;
  for(int i=1;i<=a;i++)
  {
    ax[i]=in.nextInt();
    ay[i]=in.nextInt();
  }
  while(in.hasNext())
  {
   if(in.next().equals("O"))
    {
    int w=in.nextInt();
    if(bool[w]==1) continue;
    for(int j=1;j<=a;j++)
     {
       if(bool[j]==0) continue;
       int u=j;
       while(arr[u]!=u)
        u=arr[u];
       int l=w;
       while(arr[l]!=l)
        l=arr[l];
       if(l==u) continue;
       int x=ax[w]-ax[j];
       int y=ay[w]-ay[j];
       if(x*x+y*y<=max)
        {
        if(u>l) arr[j]=arr[w]=arr[u]=l;
        else arr[j]=arr[w]=arr[l]=u;
        }
      }
    bool[w]=1;
     }
     else
     {
    int r=in.nextInt(),w=r;
    while(arr[w]!=w)
       w=arr[w];
    int t=in.nextInt(),u=t;
    while(arr[u]!=u)
       u=arr[u];
    arr[r]=w;
    arr[t]=u;
    if(arr[w]==arr[u]&&bool[w]==1) System.out.println("SUCCESS");
    else System.out.println("FAIL");
      }
   }
 }
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *