12771번: Oil

https://www.acmicpc.net/problem/12771


$O(n^2\lg n)$

답에 해당하는 시추드릴이 나타내는 직선을 그렸을 때, 언제나 이 직선이 관통하고 있는 석유층 중 하나의 왼쪽 끝 지점에 닿도록 평행이동시킬 수 있다.
따라서 답은 어느 한 석유층의 왼쪽 끝점을 지나는 직선을 그을 때 관통하는 최대 석유층 개수라고 보아도 된다.

이제 i번 석유층의 왼쪽 끝지점 u를 지나는 직선을 그을 때 관통할 수 있는 최대 석유층 개수를 구해보자.
u를 지나는 석유층과 평행한 직선 l을 생각하고 이를 u를 회전축으로 반시계 방향으로 회전시키는 모습을 상상해보자.
모든 석유층은 l이 회전함에 따라 관통하기 시작했다가 다시 관통하지 않게 될 것이다.
즉, 석유층(i)마다 l이 해당 석유층을 관통하는 l의 회전각 구간 [xi, yi]을 표현할 수 있고
한 지점에서 해당 구간들이 가장 많이 겹칠 때 그 개수가 답이 된다.

* 최대로 많이 겹칠 때 개수를 구하는 방법은 https://www.acmicpc.net/problem/11000 문제 풀이와 동일하다.

이를 구현할 때는 회전각을 이용하는 것보다 ccw 공식을 통해 상대적인 회전 정도를 비교하는 편이 계산 정확도면에서 훨씬 좋다.
먼저, u와 같은 y값을 가진 석유층을 제외하고 u보다 y값이 작은 양 끝점들은 u에 대해 점대칭 시킨다.
그리고 나서 ccw공식을 이용하여 각 점들을 반시계 방향으로 정렬시킨다.
이제 정렬된 순서대로 들어오는 점들에 대해 선분 왼쪽 끝점이면 석유량을 증가시키고, 오른쪽 끝점이면 가중치를 차감시키면서 최대 누적량을 구한다.

#include<cstdio>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int MXN = 2e3;
typedef long long ll;
int n, r;
pair<ll, ll> o;
struct st {
    pair<ll, ll> t;
    int v;
    bool operator<(st i) const {
        ll ccw = (t.x - o.x)*(i.t.y - o.y) - (t.y - o.y)*(i.t.x - o.x);
        return ccw<0 || !ccw&&v>i.v;
    }
}p[MXN * 2], q[MXN * 2];
int main() {
    scanf("%d", &n);
    for (int i = 0, x0, x1, y; i < n; i++) {
        scanf("%d%d%d", &x0, &x1, &y);
        p[i] = { { min(x0,x1),y },abs(x0 - x1) };
        p[i + n] = { { max(x0,x1),y },-abs(x0 - x1) };
    }
    for (int i = 0; i < n; i++) {
        int sz = 0, s = p[i].v;
        o = p[i].t;
        for (int j = 0; j < 2 * n; j++) {
            if (o.y < p[j].t.y) q[sz++] = p[j];
            if (o.y > p[j].t.y) q[sz++] = { { 2 * o.x - p[j].t.x,2 * o.y - p[j].t.y },-p[j].v };
        }
        sort(q, q + sz);
        for (int j = 0; j < sz; j++) r = max(r, s += q[j].v);
        r = max(r, s);
    }
    printf("%d", r);
    return 0;
}