2020-7-5

질문 G: BUREK
시간 제한: 1 Sec  메모리 제한: 128 MB 제출 상태.
제목 설명
베 이 커 금 보 는 N 개의 삼각형 이 있다.그의 아들 조 이 는 삼각형 을 자 르 려 고 큰 칼 을 가지 고 있다.매번 절단 할 때마다 조 이 는 x 축 과 평행 하 는 직선 (y = c) 또는 y 축 과 평행 하 는 직선 (x = c) 으로 이 삼각형 들 을 절단 할 수 있다.당신 의 임 무 는 매번 절단 할 때마다 몇 개의 삼각형 이 절단 되 는 지 계산 하 는 것 입 니 다.주의: 잘 린 삼각형 은 여전히 삼각형 으로 간주 합 니 다.삼각형 이 잘 리 고 삼각형 이 직선 에서 왼쪽 부분의 면적 과 직선 에서 오른쪽 부분의 면적 만 0 보다 커 야 한다.
입력
첫 번 째 줄 은 정수 N (2 < = N < = 100000), 삼각형 의 개수 이다.2 번 부터 N + 1 줄 마다 6 개의 정수 x1, y1, x2, y2, x3, y3 은 삼각형 의 세 개의 정점 (x1, y1), (x2, y2), (x3, y3) (이 세 개의 점 이 일치 하지 않 음 을 보증 합 니 다) 0 < = x1, y1, x2, y2, x3, y3 < = 1000000 번 째 N + 2 줄 은 정수 M (2 < = M < = 100000) 이 고 절단 횟수 입 니 다.N + 3 부터 N + M + 2 행 까지 직선 방정식 인 'x = c' 또는 'y = c' (등호 양쪽 의 빈 칸 주의) 0 < = c < = 1000000 을 포함한다.
출력
절단 할 때마다 절단 한 삼각형 의 수량 을 출력 합 니 다.
샘플 입력 Copy

【  1】
3  
1 0 0 2 2 2  
1 3 3 5 4 0  
5 4 4 5 4 4  
4  
x = 4  
x = 1  
y = 3  
y = 1
【  2】
4  
2 7 6 0 0 5  
7 1 7 10 11 11  
5 10 2 9 6 8  
1 9 10 10 4 1 
4  
y = 6  
x = 2  
x = 4  
x = 9

샘플 출력 Copy

【  1】
0  
1  
1  
2
【  2】
3  
2  
3  
2 

제시 하 다.
최소 40% 의 데이터 M < = 300 의 다른 40% 의 데이터 삼각형 정점 의 좌 표 는 1000 보다 작다.
사실은 접두사 와 삼각형 이 절 단 된 범 위 는 직사각형 이다.
문 제 를 내 면 이것 을 제출 하 세 요. windows 시스템 에서 Liux 와 줄 바 꿈 기호 가 다 르 기 때 문 입 니 다.

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include 
#include 
using namespace std;
int qzx[1000005];
int qzy[1000005];
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        int x1,x2,x3,y1,y2,y3;
        scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);
        int minx=x1,miny=y1,maxx=x1,maxy=y1;
        minx=min(minx,x2);
        minx=min(minx,x3);
        miny=min(miny,y2);
        miny=min(miny,y3);
        maxy=max(maxy,y2);
        maxy=max(maxy,y3);
        maxx=max(maxx,x2);
        maxx=max(maxx,x3);
        if(maxx-minx==1||maxx-minx==0)
        {
           ///  
        }
        else
        {
            qzx[minx+1]++;
            qzx[maxx]--;
        }
        if(maxy-miny==1||maxy-miny==0)
        {
               ///  
        }
        else
        {
            qzy[miny+1]++;
            qzy[maxy]--;
        }
    }
    for(int i=1; i<=1000005; i++)
    {
        qzx[i]+=qzx[i-1];
    }
    for(int i=1; i<=1000005; i++)
    {
        qzy[i]+=qzy[i-1];
    }
    int m;
    scanf("%d",&m);
    char ch;
    int d;
    getchar();
    getchar();
   // getchar();
    for(int i=1; i<=m; i++)
    {
        scanf("%c",&ch);
        // printf("%c
",ch);
        getchar();
        getchar();
        scanf("%d",&d);
        if(i!=m)
        {
           // getchar();
            getchar();
            getchar();
        }
        if(ch=='x')
        {
                printf("%d
",qzx[d]);
        }
        else
        {
                printf("%d
",qzy[d]);
        }
    }
    return 0;

}

windows 테스트 용 다음 코드. 

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include 
#include 
using namespace std;
int qzx[1000005];
int qzy[1000005];
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        int x1,x2,x3,y1,y2,y3;
        scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);
        int minx=x1,miny=y1,maxx=x1,maxy=y1;
        minx=min(minx,x2);
        minx=min(minx,x3);
        miny=min(miny,y2);
        miny=min(miny,y3);
        maxy=max(maxy,y2);
        maxy=max(maxy,y3);
        maxx=max(maxx,x2);
        maxx=max(maxx,x3);
        if(maxx-minx==1||maxx-minx==0)
        {
           ///  
        }
        else
        {
            qzx[minx+1]++;
            qzx[maxx]--;
        }
        if(maxy-miny==1||maxy-miny==0)
        {
               ///  
        }
        else
        {
            qzy[miny+1]++;
            qzy[maxy]--;
        }
    }
    for(int i=1; i<=1000005; i++)
    {
        qzx[i]+=qzx[i-1];
    }
    for(int i=1; i<=1000005; i++)
    {
        qzy[i]+=qzy[i-1];
    }
    int m;
    scanf("%d",&m);
    char ch;
    int d;
    getchar();
    getchar();
    getchar();
    for(int i=1; i<=m; i++)
    {
        scanf("%c",&ch);
        // printf("%c
",ch);
        getchar();
        getchar();
        scanf("%d",&d);
        if(i!=m)
        {
           getchar();
            getchar();
            getchar();
        }
        if(ch=='x')
        {
                printf("%d
",qzx[d]);
        }
        else
        {
                printf("%d
",qzy[d]);
        }
    }
    return 0;

}