Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 2318tijie

Posted by xvguochen at 2016-07-13 14:35:58 on Problem 3304
```#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,bx1,bx2,by1,by2;
struct node
{
int x,y;
}up[1100000],down[1100000];
int a[1100000];
int multi(node p0,node p1,node p2)
{
int x1=p1.x-p0.x;
int y1=p1.y-p0.y;
int x2=p2.x-p0.x;
int y2=p2.y-p0.y;
if((x1*y2-x2*y1)<=0)return 1;
else return 0;
}
void check(node p0)
{
int l=0,r=n+1,kk;
while(l<=r)
{
int mid=(l+r)/2;
if(!multi(p0,up[mid],down[mid]))
{
kk=mid;
l=mid+1;
}
else r=mid-1;
}
a[kk]++;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==0)break;
scanf("%d%d%d%d%d",&m,&bx1,&by1,&bx2,&by2);
memset(a,0,sizeof(a));
up[0].x=bx1;up[0].y=by1;
down[0].x=bx1;down[0].y=by2;
up[n+1].x=bx2;up[n+1].y=by1;
down[n+1].x=bx2;down[n+1].y=by2;
for(int i=1;i<=n;i++)
{
int x,y;scanf("%d%d",&x,&y);
up[i].x=x;up[i].y=by1;
down[i].x=y;down[i].y=by2;
}
for(int i=1;i<=m;i++)
{
node toy;scanf("%d%d",&toy.x,&toy.y);
check(toy);
}
for(int i=0;i<=n;i++)printf("%d: %d\n",i,a[i]);
printf("\n");
}
return 0;
}```

Followed by: