Source Code

Problem: 1066  User: yzhw 
Memory: 912K  Time: 3641MS 
Language: Java  Result: Accepted 

Source Code 
import java.io.*;
import java.util.Arrays;
class point
{
	double x1,x2,y1,y2;
}
public class Main {

	static double M(double x1,double y1,double x2,double y2,double x0,double y0)
	{
		return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
	}
	static boolean cross(point u,point v)
	{
		if(Math.max(u.x1, u.x2)>=Math.min(v.x1,v.x2)&&
		   Math.max(v.x1,v.x2)>=Math.min(u.x1, u.x2)&&
		   Math.max(u.y1, u.y2)>=Math.min(v.y1,v.y2)&&
		   Math.max(v.y1, v.y2)>=Math.min(u.y1, u.y2)&&
		   (M(u.x1,u.y1,v.x1,v.y1,v.x2,v.y2)*M(u.x2,u.y2,v.x1,v.y1,v.x2,v.y2)<0)&&
		   (M(v.x1,v.y1,u.x1,u.y1,u.x2,u.y2)*M(v.x2,v.y2,u.x1,u.y1,u.x2,u.y2)<0)
	      )
	     
		   return true;
		else return false;
	}
	static boolean equal(double a,double b)
	{
		if(Math.abs(a-b)<1e-7) return true;
		else return false;
	}
	public static void main(String[] args) throws IOException{
		StreamTokenizer in=new StreamTokenizer(System.in);
		int num;
		double endx,endy;
		in.nextToken();
		num=(int)in.nval;
		point data[]=new point[num+1];
		int[] up=new int[101],down=new int[101],left=new int[101],right=new int[101];
		int uc=1,dc=1,lc=1,rc=1;
		for(int i=1;i<=num;i++)
		{
			data[i]=new point();
			in.nextToken();
			data[i].x1=in.nval;
			in.nextToken();
			data[i].y1=in.nval;
			in.nextToken();
			data[i].x2=in.nval;
			in.nextToken();
			data[i].y2=in.nval;
			if(equal(data[i].x1,0)) left[++lc]=(int)data[i].y1;
			if(equal(data[i].x2,0)) left[++lc]=(int)data[i].y2;
			if(equal(data[i].x1,100)) right[++rc]=(int)data[i].y1;
			if(equal(data[i].x2,100)) right[++rc]=(int)data[i].y2;
			if(equal(data[i].y1,0)) down[++dc]=(int)data[i].x1;
			if(equal(data[i].y2,0)) down[++dc]=(int)data[i].x2;
			if(equal(data[i].y1,100)) up[++uc]=(int)data[i].x1;
			if(equal(data[i].y2,100)) up[++uc]=(int)data[i].x2;
		}
		up[++uc]=100;
		down[++dc]=100;
		left[++lc]=100;
		right[++rc]=100;
		in.nextToken();
		endx=in.nval;
		in.nextToken();
		endy=in.nval;
		Arrays.sort(left,1,lc+1);
		Arrays.sort(right,1,rc+1);
		Arrays.sort(up,1,uc+1);
		Arrays.sort(down,1,dc+1);
		double[] cup=new double[uc],cdown=new double[dc],cleft=new double[lc],cright=new double[rc];
		for(int i=1;i<uc;i++) cup[i]=(double)(up[i]+up[i+1])/2;
		for(int i=1;i<dc;i++) cdown[i]=(double)(down[i]+down[i+1])/2;
		for(int i=1;i<rc;i++) cright[i]=(double)(right[i]+right[i+1])/2;
		for(int i=1;i<lc;i++) cleft[i]=(double)(left[i]+left[i+1])/2;
		//---------------------------deal------------------------------------------------------
		int res=9999999;
		point temp=new point();
		temp.x2=endx;
		temp.y2=endy;
		for(int i=1;i<uc;i++)
		{
		  	temp.x1=cup[i];
		  	temp.y1=100;
		  	int count=0;
		  	for(int j=1;j<=num;j++)
		  		if(cross(data[j],temp)) count++;
		  	if(count<res) res=count;
		}
		for(int i=1;i<dc;i++)
		{
		  	temp.x1=cdown[i];
		  	temp.y1=0;
		  	int count=0;
		  	for(int j=1;j<=num;j++)
		  		if(cross(data[j],temp)) count++;
		  	if(count<res) res=count;
		}
		for(int i=1;i<lc;i++)
		{
		  	temp.x1=0;
		  	temp.y1=cleft[i];
		  	int count=0;
		  	for(int j=1;j<=num;j++)
		  		if(cross(data[j],temp)) count++;
		  	if(count<res) res=count;
		}
		for(int i=1;i<rc;i++)
		{
		  	temp.x1=100;
		  	temp.y1=cright[i];
		  	int count=0;
		  	for(int j=1;j<=num;j++)
		  		if(cross(data[j],temp)) count++;
		  	if(count<res) res=count;
		}
		res++;
		System.out.println("Number of doors = "+res);
		
		
			
			
		}

	}