[기하학] [HNOI 2008] [BZOJ 1007] 수평 가시 직선

제목 설명
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 개의 직선 두 개가 겹 치지 않 습 니 다. 보 이 는 모든 직선 을 구 합 니 다.
첫 번 째 행위 N (0 < N < 50000), 다음 N 줄 입력 Ai, Bi
작은 출력 에서 직선 번 호 를 볼 수 있 고 두 중간 은 빈 칸 으로 구분 되 며 마지막 숫자 뒤에 도 빈 칸 이 있어 야 합 니 다.
샘플 입력
3 -1 0 1 0 0 0
샘플 출력
1 2
제목 분석
먼저 우 리 는 문 제 를 보면 알 수 있 듯 이 우 리 는 아래 의 돌출 가방 을 유지 하고 있다. 그러면 우 리 는 경사 율 최적화 방법 에 따라 해 보 자. 먼저 우 리 는 모든 직선 을 K 에 따라 정렬 한 다음 에 우 리 는 위의 교점 이 현재 직선 아래 에 있다 면 현재 직선 은 반드시 위의 직선 을 덮 었 을 것 이다. 이 그림 은 그림 을 그리 면 알 수 있다.그리고 마지막 스 택 에 남 은 직선 이 답 입 니 다.
코드

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
#include <cmath>
#define mcp(a,b) fabs((a)-(b))<eps
using namespace std;
const int MAXN = 500000;
const double eps = 1e-8;
const int INF = 1000000000;
struct Point{
    double x, y;
    Point(){x=y=0;}
};
struct Line{
    double a, b;
    int id;
    Point GetD(const Line& c){
        Point ret;
        ret.x = (1.0 * (c.b - b)) / (a - c.a);
        ret.y = a * ret.x + b;
        return ret;
    }
    bool operator == (const Line& c) {
        return c.a + eps >= a && c.a - eps <= a;
    }
}T[MAXN+10];
stack<Line> ans;
stack<Point> jd;
bool cmp(Line a, Line b){
    if(mcp(a.a, b.a))
        return a.b < b.b;
    return a.a < b.a;
}
int pcmp(Point p, Line l){
    double y = l.a * p.x + l.b;
    if(y >= p.y-eps)
        return -1;
    return 1;
}
bool check[MAXN+10];
int main(){
    Point tmp;
    int n, tn=0;
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf", &T[i].a, &T[i].b);
        T[i].id = i;
    }
    sort(T+1, T+1+n, cmp);
    for(int i=1;i<=n;i++){
        while(mcp(T[i].a,T[i+1].a)) i++;
        T[++tn] = T[i];
    }
    ans.push(T[1]);
    for(int i=2;i<=tn;i++){
        while(!jd.empty()){
            Point tp = jd.top();
            if(pcmp(tp, T[i]) <= 0){
                jd.pop();
                ans.pop();
            }else break;
        }
        jd.push(T[i].GetD(ans.top()));
        ans.push(T[i]);
    }
    while(!ans.empty()){
        check[ans.top().id] = true;
        ans.pop();
    }
    bool fir = false;
    for(int i=1;i<=n;i++)
        if(check[i]){
            if(fir)
                printf(" %d", i);
            else{
                printf("%d", i);
                fir = true;
            }
        }

    return 0;
}