BUREK

Description
Baker  Crumble  has  just  baked N triangular  burek
2
 pastries.  Each  pastry  can  be  represented  in  the
Cartesian coordinate system as a 易做图 with vertices in integer coordinate points.
The baker's mischievous son Joey has just taken a large knife and started to cut the pastries. Each cut
that Joey makes corresponds to a horizontal (y = c) or vertical (x = c) line in the coordinate  system.
Help the baker assess the damage caused by Joey's pastry cutting. Your task is to determine, for each
Joey's cut, how many pastries are affected (such that both the left and right parts of the cut pastry have
areas greater than zero).

Input
The first line of input contains the positive integer N (2 ≤ N ≤ 100 000), the number of burek pastries.
Each of the following N lines contains six nonnegative integers smaller than 10
6
. These numbers are, in
order, the coordinates (x1, y1), (x2, y2), (x3, y3) of the three pastry-易做图 vertices. The three vertices will
not all be on the same line. The pastries can touch as well as overlap.
The following line contains the positive integer M (2 ≤ M ≤ 100 000), the number of cuts.
Each of the following M lines contains a single cut line equation: “x = c” or “y = c” (note the spaces
around the equals sign), where c is a nonnegative integer smaller than 10
6
.

Output
For each cut, output a line containing the required number of cut pastries.

Sample Input
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
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
Sample Output
0
1
1
2
3
2
3
2
HINT

In test data worth at least 40 points, M ≤ 300.

In  test  data  worth an additional 40 points, the  vertex  coordinates  of  all  易做图s  will  be  smaller  than

1000.

分析：分两边处理，先从六个数找出x最大最小、y最大最小四个数，如为x=n轴时，只需搜索小于n的x最大的所有数a，大于n的x最小的所有数b，答案即是n-a-b，y轴时亦同样分析。

代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX=1000000;
int num[4][MAX+2];
int main()
{
    int n,m,i,ans,in;
    while(scanf("%d",&n)!=EOF)
    {
        memset(num,0,sizeof(num));
        for(i=0;i<n;i++)
        {
            int x1,y1,x2,y2,x3,y3,max_x,max_y,min_x,min_y;
            scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);
            max_x=max(x1,max(x2,x3));
            min_x=min(x1,min(x2,x3));
            max_y=max(y1,max(y2,y3));
            min_y=min(y1,min(y2,y3));
            num[0][max_x]++;
            num[1][min_x]++;
            num[2][max_y]++;
            num[3][min_y]++;
        }
        for(i=1;i<=MAX;i++)
        {
            num[0][i]+=num[0][i-1];
            num[2][i]+=num[2][i-1];
        }
        for(i=MAX-1;i>=0;i--)
        {
            num[1][i]+=num[1][i+1];
            num[3][i]+=num[3][i+1];
        }
        scanf("%d",&m);
        while(m--)
        {
            char word;
            scanf(" %c = %d",&word,&in);
            if(word=='x')
                ans=n-num[0][in]-num[1][in];
            else
                ans=n-num[2][in]-num[3][in];
            printf("%d\n",ans);
        }
    }
    return 0;
}

补充：软件开发 , C++ ,

上一个：hdu 2187
下一个：HDU4686[矩阵快速幂]