글 읽기 - 고수님들의 도움이 시급합니다

ahn 6년 전 1

테스트를 돌리면 54%까지는 통과하나, 이후부터는 틀렸습니다가 나옵니다..
코드에 대해서 간단히 설명드리면 최하단 y축, 최자측 x축에 위치한 점을 시작점으로 잡은 후

각 점들의 각도를 기준으로 반시계 방향으로 정렬을 합니다.

이후에 벡터 외적을 하여 블록체인을 생성하게 되는데..

일직선상에 위치한 선들의 경우 정답이 2가 나옵니다.. 제가 생각하지 못한 반례가 있는 걸까요? ㅠㅠ
고수님들의 도움이 필요합니다ㅠㅠㅠㅠ

​

using System;
using System.Collections.Generic;

namespace BOJ
{
    class Program
    {
        public static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            Point[] arr = new Point[n];
            Stack<Point> stack = new Stack<Point>();
            Stack<Point> vertax = new Stack<Point>(); ;//현재선의 시작점

            while (n-- > 0)
            {
                string[] arg = Console.ReadLine().Split(' ');
                arr[n] = new Point(int.Parse(arg[0]), int.Parse(arg[1]));
            }
            Array.Sort(arr); //y축 최하단, x축 최좌측 좌표를 구하기 위해 소트 한다.
            Point start = arr[0];

            for (int i = 1; i < arr.Length; i++)//기준점에서 각 점들의 상대적 세타를 구한다
                arr[i].seta = Math.Atan2(arr[i].y - arr[0].y, arr[i].x - arr[0].x) * 180 / Math.PI;

            Array.Sort(arr, new SetaSort()); // 세타를 기반으로 반시계 방향으로 소트한다.

            stack.Push(start); //기준좌표를 스택에 푸쉬
            stack.Push(arr[1]); //시작선을 위한 점
            vertax.Push(start);

            for (int i = 2; i < arr.Length; i++) //모든좌표를 반시계방향으로 순회
            {
                while (stack.Count >= 2)
                {
                    var item = stack.Peek();
                    var currentVertax = vertax.Peek();
                    Point VectorA = new Point(item.x - currentVertax.x, item.y - currentVertax.y);
                    Point VectorB = new Point(arr[i].x - currentVertax.x, arr[i].y - currentVertax.y);
                    long ccw = VectorA.x * VectorB.y - VectorA.y * VectorB.x; //벡터 외적 연산
                    if (ccw > 0)//왼쪽에 위치해있다면
                    {
                        break;
                    }
                    else //점이 오른쪽에 위치해있다면
                    {
                        vertax.Pop();
                        stack.Pop();
                    }
                }
                vertax.Push(stack.Peek()); //벡터A, 벡터B의 원점을 변경
                stack.Push(arr[i]);
            }

            //foreach (var item in stack)
            //{
            //    Console.WriteLine("x:{0} y:{1}", item.x, item.y);
            //}
            Console.WriteLine(stack.Count);
        }
        class Point : IComparable<Point>
        {
            public int x, y;
            public double seta = 0;
            public Point(int x, int y)
            {
                this.x = x;
                this.y = y;
            }

            public int CompareTo(Point other)
            {
                int res = 0;
                if (y > other.y) res = 1;
                else if (y < other.y) res = -1;
                else
                {
                    if (x > other.x) res = 1;
                    else if (x < other.x) res = -1;
                }
                return res;
            }
        }

        class SetaSort : IComparer<Point>
        {
            public int Compare(Point x, Point y)
            {
                int res = 0;
                if (x.seta < y.seta) res = -1;
                else if (x.seta > y.seta) res = 1;
                return res;
            }
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

고수님들의 도움이 시급합니다

ahn 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말