15807 - *빛*영*우*

 

 

step 1

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

step 2

그림을 반시계 방향으로 45도 돌린다고 생각해 봅시다. 그럼 위 문제를 푸는 것과 같습니다.

새로운 좌표축 2개를 도입합니다. 하나는 $y=x$고 다른 하나는 $y=-x$입니다. 새로운 좌표 축에 맞춰 좌표를 재설정하고 위 문제를 해결합니다.

축을 바꾸는 것을 해봅시다. 

위 그림에서 점 $A$는 원래 축 기준 (1,3)에 있습니다. 그리고 새로운 축(빨간색) 기준으로는 (-2, 4)에 있습니다. 원래 축 기준 $x$좌표를 $X$, 원래 축 기준 $y$좌표를 $Y$라고 하면

바뀐 축 기준 $x$좌표 : $X-Y$

바뀐 축 기준 $y$좌표 : $X+Y$

로 쉽게 계산할 수 있습니다. 

step 3

이제부터 모든 좌표는 바뀐 축 기준으로 설명하겠습니다.

입력받은 모든 좌표를 $x$좌표가 큰 값부터, $x$가 같으면 $y$좌표가 작은 값부터 오도록 정렬합니다. 세그먼트 트리를 이용해 라이트들을 관리할 것입니다.

좌표들을 처음부터 쭉 살펴봅니다. 만약 라이트가 있다면 라이트의 $y$좌표에 해당하는 새그트리 위치에 1을 더해줍니다. 만약 지점이 있다면 지금까지 만난 모든 라이트 들 중 라이트의 $y$좌표가 지점의 $y$좌표보다 작은 것들의 개수를 세어 줍니다. 해당 라이트는 반드시 지점을 비추고 아닌 라이트는 절대 지점을 비추지 않습니다. 이 동작을 세그트리로 구현합니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
int it[30000],t=1,d[300000];
struct data {
    int x, y,t,i;
    inline bool operator<(const data& temp)const {
        return x>temp.x || x==temp.x && y<temp.y || x==temp.x && y==temp.y && t<temp.t;
    }
}b[300000];
void up(int s, int e, int i, int x, int y) {
    if (x <= s && e <= y) {
        it[i]++;
        return;
    }
    if (e < x || y < s) return;
    up(s, (s + e) / 2, i * 2, x, y);
    up((s + e) / 2 + 1, e, i * 2 + 1, x, y);
}
int find(int i) {
    int cnt = it[i];
    while (i != 1) {
        i /= 2;
        cnt += it[i];
    }
    return cnt;
}
int main() {
    int i,n,m;
    scanf("%d", &n);
    for (i = 1;i <= n;i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        b[i].t = 1;
        b[i].x = x - y;
        b[i].y = x + y;
    }
    scanf("%d", &m);
    for (i = n+1;i <= n+m;i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        b[i].t = 2;
        b[i].x = x - y;
        b[i].y = x + y;
        b[i].i = i-n;
    }
    n += m;
    while (t < 6001) t <<= 1;
    sort(b + 1, b + n + 1);
    for (i = 1;i <= n;i++) {
        if (b[i].t == 1) {
            up(1, t, 1, b[i].y + 3001, 6001);
        }
        else {
            d[b[i].i] = find(t - 1 + b[i].y + 3001);
        }
    }
    for (i = 1;i <= m;i++) {
        printf("%d\n", d[i]);
    }
    return 0;
}