BZOJ 1007: [HNOI 2008] 수평 가시 직선 창고 / 계산 기하학

1007: [HNOI 2008] 수평 가시 직선
Time Limit: 1 Sec  Memory Limit: 162 MB
제목 연결
http://www.lydsy.com/JudgeOnline/problem.php?id=1007
Description
 xoy 직각 좌표 평면 에 n 개의 직선 L1, L2,... Ln 이 있 는데 Y 값 이 무한 한 곳 에서 아래 를 내 려 다 보면 Li 의 특정한 서브 라인 을 볼 수 있 고 Li 를 볼 수 있 는 것 이 라 고 부 릅 니 다. 그렇지 않 으 면 Li 는 덮 인 것 입 니 다.
    예 를 들 어 직선 에 대해:
    L1:y=x; L2:y=-x; L3:y=0
    L1 과 L2 는 볼 수 있 고 L3 는 덮 여 있다.
    n 개의 직선 을 제시 하여 y = Ax + B 의 형식 (| A |, | B | < = 500000) 을 표시 하고 n 개의 직선 두 개가 겹 치지 않 습 니 다. 보 이 는 모든 직선 을 구 합 니 다.
Input
첫 번 째 행위 N (0 < N < 50000), 다음 N 줄 입력 Ai, Bi
Output
작은 출력 에서 직선 번 호 를 볼 수 있 고 두 중간 은 빈 칸 으로 구분 되 며 마지막 숫자 뒤에 도 빈 칸 이 있어 야 합 니 다.
Sample Input
3 -1 0 1 0 0 0
Sample Output
1 2
HINT
문제 풀이:
우선 우 리 는 경사 율 에 따라 큰 것 에서 작은 것 으로 정렬 한 다음 에 우 리 는 한 무더기 에 대해 최적화 시킨다.
만약 한 직선 을 삽입 하려 고 한다 면, K 의 가장 큰 선과 K 의 가장 작은 선 은 틀림없이 등 을 덮 지 않 고, 중간의 그 직선 만 눌 릴 것 이다
그 러 니까 판정 하고 계속 업데이트 하면 돼 요.
구체 적 인 판정 은 보다 경사 율 이 작은 직선 과 경사 율 중간의 직선, 경사 율 이 작은 직선 과 경사 율 이 큰 직선, 이 두 x 의 좌표 크기 를 비교 한 다음 에 하면 됩 니 다 ~
코드:
 

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 50001

#define mod 10007

#define eps 1e-9

//const int inf=0x7fffffff;   //   

const int inf=0x3f3f3f3f;

/*



*/

//**************************************************************************************

struct node

{

    double x,y;

    int id;

};

bool cmp(node c,node d)

{

    return c.x>d.x;

}

double kiss(node a,node b)

{

    return (b.y-a.y+0.0)/(a.x-b.x+0.0);

}

node a[maxn],aa[maxn];

int s[maxn];

inline ll read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

bool cmp2(int c,int d)

{

    return a[c].id<a[d].id;

}

int main()

{

    int n;

    cin>>n;

    for(int i=1;i<=n;i++)

    {

        cin>>aa[i].x>>aa[i].y;

        aa[i].id=i;

    }

    sort(aa+1,aa+n+1,cmp);

    int M=0;

    for(int i=1;i<=n;i++)

    {

        if(aa[i].x!=a[i-1].x) 

            a[++M]=aa[i];

        else if(aa[i].y>a[M].y) 

            a[M].y=aa[i].y,a[M].id=aa[i].id;            

    }

    int top=0;

    s[1]=1;top=1;

    for(int i=2;i<=M;i++)

    {

        while(top>=2)

        {

            double x1=kiss(a[s[top-1]],a[i]);

            double x2=kiss(a[s[top]],a[i]);

            if(x1<=x2+1e-6)

                top--;

            else

                break;

        }

        s[++top]=i;

    }

    sort(s+1,s+top+1,cmp2);

    for(int i=1;i<=top;i++)

        cout<<a[s[i]].id<<" ";

    return 0;

}