题意 ： 给你n块板的坐标，m个玩具的具体坐标，2318中板是有序的，而2398无序需要自己排序，2318要求输出的是每个区间内的玩具数，而2318要求输出的是有 i 个玩具的区间有几个。
思路 ： 两个题基本差不多，只不过2398排一下序，然后再找个数组标记一下就行。
这个题我一开始没想到用二分，判断了点在四边形内但是没写下去，然后看了网上的二分区间，利用叉积判断点在左边还是右边。
2318代码：
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream> using namespace std ; struct point
{
int x,y ;
}p ;
struct line
{
point a,b ;
} eline[] ; int s[] ; int xmult(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y) ;
} void binary_searc(point p,int a)
{
int l = , r = a- ,mid ;
while(l < r)
{
mid = (l + r) / ;
if(xmult(p,eline[mid].a,eline[mid].b) > ) l = mid+ ;
else r = mid ;
}
if(xmult(p,eline[l].a,eline[l].b) < ) s[l] ++ ;
else s[l+] ++ ;
}
int main()
{
int m,n,x1,x2,y1,y2 ;
while(scanf("%d",&n) != EOF)
{
if(n == ) break ;
scanf("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2) ;
memset(s,,sizeof(s)) ;
for(int i = ; i < n ; i++)
{
scanf("%d %d",&eline[i].a.x,&eline[i].b.x) ;
eline[i].a.y = y1 ;
eline[i].b.y = y2 ;
}
for(int i = ; i < m ; i++)
{
scanf("%d %d",&p.x,&p.y) ;
binary_searc(p,n) ;
}
for(int i = ; i <= n ; i++)
printf("%d: %d\n",i,s[i]) ;
printf("\n") ;
}
return ;
}
2398代码 ：
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm> using namespace std ; struct point
{
int x,y ;
}p ;
struct line
{
point a,b ;
} eline[] ; int s[],s1[] ; int xmult(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y) ;
} int cmp(const line &aa,const line &bb)
{
if (min(aa.a.x, aa.b.x) == min(bb.a.x, aa.b.x))
return max(aa.a.x, aa.b.x) < max(bb.a.x, bb.b.x);
return min(aa.a.x, aa.b.x) < min(bb.a.x, aa.b.x);
}
void binary_searc(point p,int a)
{
int l = , r = a- ,mid ;
while(l < r)
{
mid = (l + r) / ;
if(xmult(p,eline[mid].a,eline[mid].b) > ) l = mid+ ;
else r = mid ;
}
if(xmult(p,eline[l].a,eline[l].b) < ) s[l] ++ ;
else s[l+] ++ ;
}
int main()
{
int m,n,x1,x2,y1,y2 ;
while(scanf("%d",&n) != EOF)
{
if(n == ) break ;
scanf("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2) ;
memset(s,,sizeof(s)) ;
memset(s1,,sizeof(s1)) ;
for(int i = ; i < n ; i++)
{
scanf("%d %d",&eline[i].a.x,&eline[i].b.x) ;
eline[i].a.y = y1 ;
eline[i].b.y = y2 ;
}
sort(eline,eline+n,cmp) ;
for(int i = ; i < m ; i++)
{
scanf("%d %d",&p.x,&p.y) ;
binary_searc(p,n) ;
}
for(int i = ; i <= n ; i++)
s1[s[i]] ++ ;
printf("Box\n") ;
for(int i = ; i <= m ; i++)
{
if(s1[i] != )
printf("%d: %d\n",i,s1[i]) ;
}
// for(int i = 0 ; i <= n ; i++)
// printf("%d: %d\n",i,s[i]) ;
// printf("\n") ;
}
return ;
}