글 읽기 - 1708번 로직에 따라서 했는데 틀렸다고...고수님들 고견부탁합니다.

naegeora 7년 전 1

아래 로직에 따라서 작성했는데 틀렸다고 나오네요....한 4시간동안 버그잡으려고 하는데 안잡혀서...

거의 다 한것 같은데 안되서..고수님들의 고견을 부탁합니다.

1.가장작은 y좌표,x좌표 를 기준점으로 각도순으로 정렬함. [cosine값을 내림차순 정렬함]
2. 정렬된 점들을 따라가며 연속된 세점들(P[i],P[i+1],P[i+2])에 대해 ccw이면 que에 P[i+2]를 넣고,
아니면 P[i+1]을 que에서 빼고 que에서 first/second 유지하고 P[i+2]를 다시 ccw
3. 위과정을 N 까지 돌리고 P[0]를 넣어서 CCW를 돌려서 P[N-1]을 점검함.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/*  

 */
 class Main {

	public static class comp1 implements Comparator<point> {

		@Override
		public int compare(point o1, point o2) {
			// TODO Auto-generated method stub
			 if (o2.angle==o1.angle)
				 return (int) (o1.distance-o2.distance);
			 else return (o2.angle-o1.angle>0?1:-1);
		}

	}
	static int answer,N;
	static ArrayDeque<point> que=new ArrayDeque<point>();
	public static class point implements Comparable<point>{
		long x; long y;double angle; long distance;
		point(long x, long y){
			this.x=x; 
			this.y=y;
		}
		void cos(double angle, long distance){
			this.angle=angle;
			this.distance=distance;
		}
		@Override
		public int compareTo(point o) {
			// TODO Auto-generated method stub
			if (this.y == o.y) {
				return (int) (this.x - o.x);
			} else {
				return (int) (this.y - o.y);
			}
		}
	}
	public static void main(String args[]) throws Exception{
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		point p[]=new point[N];
		for(int i=0;i<N;i++){
			p[i]=new point(sc.nextLong(),sc.nextLong());
		}
		
	
		Arrays.sort(p);
/*		System.out.println(p[0].x+" "+p[0].y);
		for(int i=0;i<N;i++){
			System.out.println(i+":"+p[i].x+" "+p[i].y);
		}*/

		
		for(int i=1;i<N;i++){
			double a=(p[i].x-p[0].x)/Math.sqrt(((p[i].x-p[0].x)*(p[i].x-p[0].x)+(p[i].y-p[0].y)*(p[i].y-p[0].y)));
			long b=((p[i].x-p[0].x)*(p[i].x-p[0].x)+(p[i].y-p[0].y)*(p[i].y-p[0].y));		
			p[i].cos(a,b);
			
		}

		Comparator< point> comp1=new comp1();
		Arrays.sort(p,1,N,comp1);

		
		que.addLast(p[0]); //point first=que.peekLast(); 
		que.addLast(p[1]); //point second=que.peekLast();
		int next=2;
		point first,second;
		while(next<N){
			while(que.size()>=2){
				
				second=que.pollLast();
				first=que.peekLast();
				if(ccw(first,second,p[next])>0){
					que.addLast(second);
					break;
				}
			}
			que.addLast(p[next++]);
		}

/*		second=que.pollLast();
		first=que.peekLast();
		if(ccw(first,second,p[0])>0){
			que.addLast(second); 
		}*/

		answer= que.size();



		sc.close();
	}

	public static long ccw(point p1, point p2, point p3) {
		return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p2.x*p1.y-p3.x*p2.y-p1.x*p3.y;		
	}

}