3260471_re.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;
import java.math.*;

public class Main
{

	public static void main(String [] args)	throws Exception
	{
		try
		{
			new Main().run();
		}
		catch (Error e)
		{
			e.printStackTrace();
		}
	}

	class Point	implements Comparable <Point>
	{
		BigInteger x, y;

		Point(String x,String y)
		{
			this.x = new BigInteger(x);
			this.y = new BigInteger(y);
		}

		public boolean equals(Point that)
		{
			return this.x.compareTo(that.x)==0&&this.y.compareTo(that.y)==0;
		}

		public int compareTo(Point that)
		{
			int vx = this.x.compareTo(that.x);
			int vy = this.y.compareTo(that.y);

			return vx==0 ? vy : vx;
		}
	}

	class Segment
	{
		Point st, ed;

		Segment(Point st,Point ed)
		{
                        this.st = new Point(st.x.toString(),st.y.toString());
                        this.ed = new Point(ed.x.toString(),ed.y.toString());
		}
	}

	int [] f;
	int [] d;
	int [] id;
	Point [] p;
	Segment [] s;
	int k, index;

	public void run()	throws Exception
	{
		Scanner in = new Scanner (System.in);
		String x, y;

		k = in.nextInt();

		p = new Point [k*2+1];
		d = new int [k*2+1];
		f = new int [k*2+1];
		id = new int [k*2+1];
		s = new Segment [k];

		for(int i = 0; i < k; i++)
		{
			x = in.next();
			y = in.next();
			p[2*i] = new Point(x,y);
			x = in.next();
			y = in.next();
			p[2*i+1] = new Point(x,y);
			s[i] = new Segment(p[2*i],p[2*i+1]);
		}
		Arrays.sort(p,0,2*k);
		index = 0;
		for(int i = 0; i < 2*k; i++)
		{
			int j = i;
			while(j < 2*k&&p[j].equals(p[i]))
			{
				id[j] = index;
                                j++;
			}
			index++;
			i = j-1;
		}
		for(int i = 0; i < k*2; i++)
		{
			f[i] = i;
		}
		for(int i = 0; i < k; i++)
		{
			int i1, i2;

			try
			{
				i1 = bsearch(s[i].st);
				i2 = bsearch(s[i].ed);
			}
			catch (Error e)
			{
				while(true)
				{
					System.out.println(e);
				}
			}
                        d[i1]++;d[i2]++;
			i1 = find(i1);
			i2 = find(i2);
			f[i1] = i2;
		}
		for(int i = 0; i < index; i++)
		{
			if(f[i]!=f[0]||d[i]%2!=0)
			{
				System.out.println("0");
				return ;
			}
		}
		System.out.println("1");
	}

	public int find(int t)
	{
		if(f[t]!=t)
			return f[t]=find(f[t]);
		else
			return f[t];
	}

	public int bsearch(Point t)
	{
		int min, max, mid;

		min = 0;max = 2*k;
		while(min <= max)
		{
			mid = (min + max) / 2;
			int v = p[mid].compareTo(t);
			if(v == 0)
			{
				return id[mid];
			}
			else
			{
				if(v > 0)
					max = mid-1;
				else
					min = mid+1;
			}
		}
		throw new Error("Elements not found");
	}
}