2009-05-20
POJ 2318 TOYS
栏目：解题报告
757 Views
http://acm.pku.edu.cn/JudgeOnline/problem?id=2318
题意：
有一矩形，N条直线(直线不相交)把矩形分成N+1个区间，然后给定M个点，求矩形每个区间内有多少个点，如下图
算法：
简单题，只要对每个点求出所在的区间然后计数，求区间时使用二分找到这个点右边或者左边的第一条直线即可，复杂度M*logN
代码：
#include<iostream>
using namespace std;
#define MAX 5005
int n, m;
double x1, y1, x2, y2;
double u[MAX], l[MAX];
double k[MAX]; // 斜率
double h;
int count[MAX];
void bsearch(double x, double y)
{
int ma = n, mi = 0, mid;
double rx;
double ydis = y – y1;
while(ma > mi)
{
mid = (ma+mi)>>1;
rx = k[mid] * ydis + u[mid];
if(rx<x)mi = mid+1;
else if(rx>x)ma = mid;
}
count[ma]++;
}
int main()
{
int i;
double x, y;
while(scanf(“%d”,&n)==1 && n)
{
memset(count, 0, sizeof(count));
scanf(“%d %lf %lf %lf %lf”,&m,&x1,&y1,&x2,&y2);
h = y2 – y1;
for(i=0;i<n;++i)
{
scanf(“%lf%lf”,&u[i], &l[i]);
k[i] = (l[i]-u[i])/h;
}
u[n] = x2; l[n] = x2; k[n] = 0;
for(i=0;i<m;++i)
{
scanf(“%lf%lf”,&x,&y);
bsearch(x, y);
}
for(i=0;i<=n;++i)
printf(“%d: %d\n”,i,count[i]);
printf(“\n”);
}
return 0;
}
