Grandpa 's Estate POJ - 1228 (돌출 극 각 서 개작)

제목 의 뜻 을 보고 와, 간단 한 부분 은 라인 사이 에 최소한 의 점 이 있 는 지 판단 하 는 거 잖 아.............................................................
이 문제 의 점 은 먼저 점 구조 에 따라 돌출 되 어야 한다. 왜냐하면 문제 가 준 데 이 터 는 반드시 돌출 된 것 이 아니 기 때문이다. 그 다음 에 우 리 는 구조 돌출 된 극 각 을 정렬 할 때 점 과 왼쪽 아래 의 점 의 각도 가 90 도 이상 일 때 거리 가 가 까 운 점 을 앞 에 배열 하기 때문에 극 각 정렬 의 알고리즘 을 고 친 다음 에 각 점 을 옮 겨 다 니 며 판단 하면 된다. 여러 점 의 공선 출력 no.그리고 바보 같은 자신 은 밤새 가방 에 잘못 쓰 고 울 었 습 니 다.

bool cmp(Point a,Point b)
{
    int ans=sgn((a-p[0])^(b-p[0]));
    if(ans==1)
        return true;
    else if(ans==0)
    {
        if(sgn(atan2(a.y,a.x)-PI/2)>=0)
            return dist(a,p[0])>dist(b,p[0]);
        else
            return dist(a,p[0])

#include 
#include 
#include 

using namespace std;

const double eps=1e-8;
const int maxn=40005;
const double PI=acos(-1.0);
int sgn(double x)
{
    if(fabs(x)=0)
            return dist(a,p[0])>dist(b,p[0]);
        else
            return dist(a,p[0])0&&((p[Stack[top]]-p[Stack[top-1]])^(p[i]-p[Stack[top-1]]))<0)
                top--;
            top++;
            Stack[top]=i;
        }
    }
}

bool vjudge()
{
    int cont=0;
    for(int i=1;i<=top;i++)
    {
        if(((p[Stack[i-1]]-p[Stack[i]])^(p[Stack[(i+1)%(top+1)]]-p[Stack[i]]))!=0)
        {
            cont++;
        }
    }
    if(cont==0)
        return false;
    cont=0;
    for(int i=1;i<=top;i++)
    {
        if(((p[Stack[i-1]]-p[Stack[i]])^(p[Stack[(i+1)%(top+1)]]-p[Stack[i]]))!=0)
        {
            if(cont==0)
                return false;
            cont=0;
        }
        else
            cont++;
        /*if(i==top)
        {
            if(cont==0)
                return false;
        }*/
    }
    return true;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        cin>>m;
        for(int i=0;i>p[i].x>>p[i].y;
        if(m<6)
        {
            cout<