USACO(Picture)

전송: http://www.nocow.cn/index.php/Translate:USACO/picture#SAMPLE_INPUT
묘사 하 다.
N (N < 5000) 사각형 포스터, 사진 과 다른 똑 같은 모양 의 사진 이 벽 에 붙 어 있다.그들의 변 은 모두 수직 이나 수평 이다.각 사각형 은 다른 사각형 을 부분적으로 또는 전부 덮어 쓸 수 있다.모든 사각형 으로 구 성 된 집합 윤곽 을 둘레 라 고 한다.프로그램 을 써 서 둘레 를 계산 하 다.
그림 1 은 7 개의 사각형 이 있 는 예 이다.
그림 1. 7 개의 사각형 의 집합
대응 하 는 윤곽 은 그림 2 의 모든 선분 의 집합 입 니 다.
그림 2. 직사각형 집합의 윤곽
모든 사각형 의 정점 좌 표 는 정수 이다.모든 좌 표 는 [- 1000, 10000] 의 범위 내 에 있 고 모든 사각형 면적 은 정수 이다.결과 의 값 은 32 비트 의 기호 정수 표시 가 필요 할 수 있 습 니 다.
격식.
PROGRAM NAME: picture
INPUT FORMAT:
(file picture.in)
INPUT FORMAT 첫 번 째 줄: N, 벽 에 붙 어 있 는 사각형 의 수 입 니 다.2. N + 1 줄 의 다음 N 줄 에는 줄 마다 두 개의 점 의 좌표 가 있 는데 각각 사각형 의 왼쪽 아래 좌표 와 오른쪽 상단 좌표 이다.모든 좌 표 는 X 좌표 와 Y 좌표 로 구성 된다.
OUTPUT FORMAT:
(file picture. out) 한 줄 만 있 고 마이너스 정수 가 아 닌 입력 데이터 의 모든 사각형 집합 윤곽 길 이 를 표시 합 니 다.
SAMPLE INPUT

7

-15 0 5 10

-5 8 20 25

15 -4 24 14

0 -6 16 4

2 15 10 22

30 10 36 20

34 0 40 16

SAMPLE OUTPUT

228

 
알고리즘 1
이산 화
모든 사각형 을 분산 시 키 는 것 (즉, 전체 평면 을 여러 개의 '세로' 또는 '가로' 로 나 누 어 조작 하 는 것) 이다. 모든 사각형 은 네 개의 변 으로 구성 되 어 세로 변 과 가로 변 으로 나 뉜 다. 세로 변 과 가로 변 을 각각 한 번 스 캔 하여 가로 변 을 예 로 들 자.

각 사각형 의 두 개의 가로 변 에서 아래 를 시작 변 이 라 고 부 르 고 위의 것 은 끝 변 이다.

각 가로 변 을 세로 좌표 로 작은 것 에서 큰 것 으로 정렬 하고 세로 좌표 가 같 으 면 시작 변 을 끝까지 배열 해 야 한다.

각 가로 변 을 차례대로 매 거 한다.

현재 변 이 시작 변 이 라면 이 변 의 가로의 모든 점 j 의 층 수 를 1, 즉 level [j] + 로 증가 시 킵 니 다. 만약 층수 가 0 에서 1 로 변 한다 면 이 점 은 반드시 가장자리 점 이 고 전체 둘레 는 ans + 입 니 다.

현재 변 이 끝 변 이 라면 이 변 의 가로의 모든 점 j 의 층 수 를 1 로 줄 이 는 것 이 level [j] 입 니 다. 층수 가 1 에서 0 으로 바 뀌 면 이 점 은 반드시 가장자리 점 이 고 총 둘레 는 ans + 입 니 다.

마찬가지 로 이 방법 에 따라 세로 변 을 스 캔 하면 최종 결 과 를 얻 을 수 있다.
알고리즘 2
총 사고방식: 이산 + 선분 수
우선 이산:

분명히 우 리 는 2n 개의 세로 선과 2n 개의 가로줄 이 있 습 니 다. 알고리즘 에서 우 리 는 세로 줄 만 생각 합 니 다. 가로 줄 의 방법 은 세로 줄 의 방법 과 같 기 때 문 입 니 다. 분 산 된 것 은 이 2n 개의 선 을 왼쪽 에서 오른쪽으로 정렬 하 는 것 입 니 다 (즉, 각 세로 줄 의 가로 좌 표를 작은 것 에서 큰 것 으로 정렬 하 는 것 입 니 다). 여기 서 필요 합 니 다 조심 하 세 요.: 같은 가로 좌표 의 세로 선 이 두 개 나타 나 면 사각형 왼쪽 에 있 는 선 은

에 배열 해 야 합 니 다.
사각형 오른쪽 에 있 는 선분 의 왼쪽 에 속 합 니 다.
그리고 선분 트 리:

각 노드 는 6 개의 속성 이 있다. s, t, l, r, c, m 는 각각 왼쪽 경계, 오른쪽 경계, 왼쪽 나무, 오른쪽 나무, 커버 수, 구간 내

를 나타 낸다.
선분 총 길이.

2n 개의 세로 선분 에 대해 사각형 왼쪽 에 있 는 선분 은 이 선분 을 선분 트 리 (커버 수 + 1) 에 추가 하고 사각형 오른쪽 에 있 는 선분 은 선

에서
단락 트 리 에서 이 구간 (덮어 쓰기 수 - 1) 을 삭제 합 니 다. 단락 을 추가, 삭제 하 는 동시에 m 속성 을 유지 해 야 합 니 다. 규칙 은 다음 과 같 습 니 다.

이 단락 의 커버 수 (c) > 0 이면 M 은 단락 의 길이 이다.

커버 수 (c) = 0 이면 M 은 왼쪽 아들 의 M + 오른쪽 아들 의 M 이다. (자체 가 잎 이 라면 0)

라인 을 조작 할 때마다 총 길 이 를 바 꿉 니 다 (변 하지 않 을 수도 있 습 니 다). 원래 길이 가 now 라면 새로운 길 이 는 new 이 고 new > now 라면 new - now 는 답 ans 입 니 다.

원본 프로그램:
/*ID: cmykrgb1PROG: pictureLANG: C++*///Written By CmYkRgB123#include #include #include #define MAX 10001using namespace std;typedef struct {    int s,t,p;    bool start;}Line;ifstream fi("picture.in");ofstream fo("picture.out");int N,ans=0;int *level;Line Lx[MAX],Ly[MAX];inline int cmp(const void *a,const void *b){    if (((Line*)a)->p==((Line*)b)->p)    {        if (((Line*)a)->start)            return -1;        else            return 1;    }    return ((Line *)a)->p < ((Line *)b)->p ? -1 : 1;}void init(){    int i,x1,x2,y1,y2;    fi >> N;    for (i=1;i<=N;i++)    {        fi >> x1 >> y2 >> x2 >> y1;        Lx[i*2-1].p=y1;        Lx[i*2-1].s=x1;        Lx[i*2-1].t=x2;        Lx[i*2-1].start=false;        Lx[i*2].p=y2;        Lx[i*2].s=x1;        Lx[i*2].t=x2;        Lx[i*2].start=true;        Ly[i*2-1].p=x1;        Ly[i*2-1].s=y2;        Ly[i*2-1].t=y1;        Ly[i*2-1].start=true;        Ly[i*2].p=x2;        Ly[i*2].s=y2;        Ly[i*2].t=y1;        Ly[i*2].start=false;    }    N*=2;    qsort(Lx+1,N,sizeof(Lx[0]),cmp);    qsort(Ly+1,N,sizeof(Ly[0]),cmp);    level=(int *)malloc(sizeof(int)*20002);    level+=10000;}void Scan(Line *L){    int i,j;    for (i=-10000;i<=10000;i++)        level[i]=0;    for (i=1;i<=N;i++)    {        if (L[i].start)        {            for (j=L[i].s;j