欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 2318 TOYS

程序员文章站 2022-04-02 16:58:51
...

题意:
一个箱子划分成n个区间,把m个玩具放到箱子里,问每个区间有几个玩具.

input :
多组样例,
第一行六个数 n ,m,x1,y1,x2,y2;
x1.y1 是箱子左上角坐标
x2,y2 是箱子右下角坐标
随后n行 每行两个数
分别是第i个区间右上角的x坐标和右下角的x坐标
ps:题目保证硬纸板分区不交叉,且给出的n行坐标按从左到右顺序给出
随后m行 每行两个数
代表第i个玩具的坐标 数据保证玩具不会再隔板上或箱子的边界上
玩具的位置顺序随机

思路:
假如一个玩具在第i个区间左侧,它一定在第x个区间左侧(x>i)
因此可以用二分判断 玩具在哪个区间里
判断某个玩具是否在一个区间左侧可以抽象成
判断一个点是否在一条直线左侧
叉积:
判断点P是否在AB左侧
PB x PA < 0 则P在AB左侧
其中
PB x PA = PA.x*PB.y - PA.y * PB.x;

代码:

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long 
#define N 5050
int ans[N];
int n,m;
struct nod{
    double x,y;
    double operator * (nod b){//重载乘号 计算叉积
        return x*b.y-y*b.x;
    }
    nod operator - (nod b){//重载减号 计算向量
        nod c;
        c.x=x-b.x;
        c.y=y-b.y;
        return c;
    }
}PA[N],PB[N];
int main()
{
    double a,b,c,d;
    while(~scanf("%d%d%lf%lf%lf%lf",&n,&m,&a,&b,&c,&d)&&n){
        memset(ans,0,sizeof(ans));
        memset(PA,0,sizeof(PA));
        memset(PB,0,sizeof(PB));
        for(int i=1;i<=n;i++){
            scanf("%lf%lf",&PA[i].x,&PB[i].x);
            PA[i].y=b;
            PB[i].y=d;
        }
        PA[n+1].x=c;//最后一个区间的右端点要记得加上
        PA[n+1].x=b;
        PB[n+1].x=c;
        PB[n+1].x=d;
        nod s;
        for(int i=1;i<=m;i++){
            scanf("%lf%lf",&s.x,&s.y);
            int l=1,r=n+1,Mid; // 二分判断
            while(l<r){
                Mid = (l+r) /2;
                nod e,f;
                e = s - PA[Mid];
                f = s - PB[Mid];
                if(e*f<0)   
                    r = Mid;
                else
                    l = Mid+1;
            }
            ans[l]++;
        }
        for(int i=1;i<=n+1;i++){
            printf("%d: %d\n",i-1,ans[i]);
        }
        printf("\n");
    }
    return 0;
}