2009-05-20
POJ 2318 TOYS
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;
}
转载注明：转自TopBoy
本站遵循：署名-非商业性使用-禁止演绎 3.0 共享协议
收藏分享：
QQ书签 /
百度收藏 /
Google书签 /
收藏到鲜果 /
Digg /
Del.icio.us
N条直线(直线不相交) 是说平行线么？如果是，为什么每条直线都有一个斜率？如果不是，只是不在矩形内相交，你的二分查找有问题。
@David
请您先看一下题目http://acm.pku.edu.cn/JudgeOnline/problem?id=2318
确切讲是被矩形切的线段是两两不相交的。
二分没有问题的。
你是不是觉得else if(rx>x)ma = mid;这句是错的？这句必须要这样写的，您认为呢？
看了原题，你的方法好像应该没问题。
我原来考虑的是，如果有隔板不是顶天立地的，如果出现隔板延长线的交点在 y1-y2 之间的，那取横线的交点就会出现乱序，这时候二分法会出错。
比如说如下的情况：
+————-
| / /
|/ /
| /
|/
|
|
+————–
@David
对，你考虑的更多一些，题目比较简单
为什么我的程序老WA啊
麻烦高手看一下：
#include
using namespace std;
int N,M;
int up_left_x,up_left_y,low_right_x,low_right_y;
struct point
{
int a,b;
}line[5005],toys[5005];
int number[5005];
void solve(int point, int left, int right)
{
int middle;
int x1,y1,x2,y2;
if(left+1==right)
{number[left]++;return;}
middle=(left+right)/2;
x1=line[middle].a-line[middle].b; y1=up_left_y-low_right_y;
x2=toys[point].a-line[middle].b; y2=toys[point].b-low_right_y;
if((x1*y2-x2*y1)>0)
solve(point,left,middle);
else
solve(point,middle,right);
}
int main()
{
int i;
int x1,y1,x2,y2,x3,y3;
while(scanf(“%d”,&N),N)
{
scanf(“%d”,&M);
scanf(“%d%d%d%d”,&up_left_x,&up_left_y,&low_right_x,&low_right_y);
for(i=1;i<=N;i++)
scanf("%d%d",&line[i].a,&line[i].b);
for(i=1;i<=M;i++)
scanf("%d%d",&toys[i].a,&toys[i].b);
memset(number,0,sizeof(number));
x1=line[1].a-line[1].b;y1=up_left_y-low_right_y;
x2=line[N].a-line[N].b;y2=up_left_y-low_right_y;
for(i=1;i0)
{number[0]++;continue;}
x3=toys[i].a-line[N].b; y3=toys[i].b-low_right_y;
if((x1*y3-y1*x3)<0)
{number[N]++;continue;}
solve(i,1,N);
}
for(i=0;i<=N;i++)
printf("%d: %d\n",i,number[i]);
printf("\n");
}
return 0;
}