博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj2318
阅读量:4597 次
发布时间:2019-06-09

本文共 1142 字,大约阅读时间需要 3 分钟。

 
#include<iostream>
#include<cstdio>
#include<algorithm>
#define eps 1e-7
#define maxn 8000
using namespace std;
#define ll long long 
struct point{
   ll x,y;
};
int n,m;
ll x1,y1,x2,y2;
point a[maxn],b[maxn];
ll mul(ll a1,ll b1,ll a2,ll b2){
return a1*b2-a2*b1;
}
bool left(point x,point y){
if(mul(x.x-y.x,x.y-y1,y.y-y.x,y2-y1)>0)return 1;
else return 0;
}
int ans[maxn];
point b1[maxn],b2[maxn];
int bn1,bn2;
void solv(int al,int ar,int bl,int br){
if(al==ar){
    ans[al]=(br-bl+1);
return;
}
int mid=(al+ar)>>1;
bn1=0;
bn2=0;
for(int i=bl;i<=br;i++){
if(left(b[i],a[mid]))b1[++bn1]=b[i];
else b2[++bn2]=b[i];
}
for(int i=bl+1;i<=bl+bn1;i++){
   b[i-1]=b1[i-bl];
}
for(int i=bl+bn1;i<=br;i++){
   b[i]=b2[i-bl-bn1+1];
}
int k1=bl+bn1;
int k2=br;
solv(al,mid,bl,bl+bn1-1);
 
solv(mid+1,ar,k1,k2);
}
int main(){
while(1){
    scanf("%d",&n);
if(n==0)break;
scanf("%d%lld%lld%lld%lld",&m,&x1,&y1,&x2,&y2);
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].y);
for(int i=1;i<=m;i++)scanf("%lld%lld",&b[i].x,&b[i].y);
solv(1,n+1,1,m);
for(int i=1;i<=n+1;i++)printf("%d: %d\n",i-1,ans[i]);
printf("\n");
}
}

转载于:https://www.cnblogs.com/wangyucheng/p/3537616.html

你可能感兴趣的文章
编译器选项
查看>>
VirtualBox虚拟机磁盘瘦身
查看>>
CSS的三种样式
查看>>
关于hadoop集群的简单性能测试——mapreduce性能,hive性能,并行计算分析(原创)...
查看>>
Asp.Net 4中使用路由时使用SiteMap
查看>>
linux之软连接 硬链接
查看>>
javascript中数组与字符串之间的转换以及字符串的替换
查看>>
使用pip安装离线包
查看>>
ORACLE 统计查看每一个表的行数
查看>>
【bzoj4281】[ONTAK2015]Związek Harcerstwa Bajtockiego 树上倍增+LCA
查看>>
Otto开发初探——微服务依赖管理新利器
查看>>
移动端开发:架构那点事!
查看>>
flex lineChart 显示所有的数据节点
查看>>
BZOJ1609 [Usaco2008 Feb]Eating Together麻烦的聚餐
查看>>
ffmpeg静态库Windows版本
查看>>
LeetCode Weekly Contest 18B
查看>>
CTS类型系统
查看>>
Cisco 交换机配置的基本命令
查看>>
MVC Filter自定义验证(拦截)
查看>>
高可用数据采集平台(如何玩转3门语言php+.net+aauto)
查看>>