2019独角兽企业重金招聘Python工程师标准>>> 
Problem D: BUREK
Time Limit: 1 Sec Memory Limit: 32 MBSubmit: 22 Solved: 14
[ Submit][ Status][ Web Board]
Description
Baker Crumble has just baked N triangular burek
2
pastries. Each pastry can be represented in the
Cartesian coordinate system as a triangle 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-triangle 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
Sample Output
HINT
In test data worth at least 40 points, M ≤ 300.
In test data worth an additional 40 points, the vertex coordinates of all triangles will be smaller than
1000.
#include <iostream>
using namespace std;
struct point{
int x, y;
};
struct tri{
point p[4];
}t[100010];
int compare(int k, char line, int num){
int dis[5];
if(line=='x'){
for(int i=1; i<=3; i++){
dis[i]=t[k].p[i].x-num;
}
if( dis[1]>=0&&dis[2]>=0&&dis[3]>=0 ||
dis[1]<=0&&dis[2]<=0&&dis[3]<=0
)
{
return 0;
}
}
else{
for(int i=1; i<=3; i++){
dis[i]=t[k].p[i].y-num;
}
if( dis[1]>=0&&dis[2]>=0&&dis[3]>=0 ||
dis[1]<=0&&dis[2]<=0&&dis[3]<=0
)
return 0;
}
return 1;
}
int
main()
{
int n, m, num, sum, ans;
char line, s[10];
char ch;
while(cin>>n){
for(int i=1; i<=n; i++){
for(int j=1; j<=3; j++){
cin>>t[i].p[j].x>>t[i].p[j].y;
}
}
cin>>m;
for(int i=1; i<=m; i++){
ans=0;
cin>>line>>ch>>num;
//cout<<line<<ch<<num<<endl;
for(int i=1; i<=n; i++){
sum=compare(i, line, num);
//cout<<sum;
ans+=sum;
}
//cout<<"**";
cout<<ans<<endl;
}
}
return 0;
}