poj 2318 TOYS(计算几何 点与线段的关系)
2024-10-07 20:54:23
TOYS
Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 12015 Accepted: 5792 Description
Calculate the number of toys that land in each bin of a partitioned toy box.
Mom and dad have a problem - their child John never puts his toys
away when he is finished playing with them. They gave John a rectangular
box to put his toys in, but John is rebellious and obeys his parents by
simply throwing his toys into the box. All the toys get mixed up, and
it is impossible for John to find his favorite toys.John's parents came up with the following idea. They put cardboard
partitions into the box. Even if John keeps throwing his toys into the
box, at least toys that get thrown into different bins stay separated.
The following diagram shows a top view of an example toy box.
For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.Input
The
input file contains one or more problems. The first line of a problem
consists of six integers, n m x1 y1 x2 y2. The number of cardboard
partitions is n (0 < n <= 5000) and the number of toys is m (0
< m <= 5000). The coordinates of the upper-left corner and the
lower-right corner of the box are (x1,y1) and (x2,y2), respectively. The
following n lines contain two integers per line, Ui Li, indicating that
the ends of the i-th cardboard partition is at the coordinates (Ui,y1)
and (Li,y2). You may assume that the cardboard partitions do not
intersect each other and that they are specified in sorted order from
left to right. The next m lines contain two integers per line, Xj Yj
specifying where the j-th toy has landed in the box. The order of the
toy locations is random. You may assume that no toy will land exactly on
a cardboard partition or outside the boundary of the box. The input is
terminated by a line consisting of a single 0.Output
The
output for each problem will be one line for each separate bin in the
toy box. For each bin, print its bin number, followed by a colon and one
space, followed by the number of toys thrown into that bin. Bins are
numbered from 0 (the leftmost bin) to n (the rightmost bin). Separate
the output of different problems by a single blank line.Sample Input
5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10
0Sample Output
0: 2
1: 1
2: 1
3: 1
4: 0
5: 1 0: 2
1: 2
2: 2
3: 2
4: 2Hint
As the example illustrates, toys that fall on the boundary of the box are "in" the box.Source
开始正经的学计算几何,恩,是的没错~
加油~
题意:给定一个长方形,在里面加上不相交的线,然后给若干点,求这些点落在哪个区域。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#define N 500015
#define INF 1000000
#define ll long long
using namespace std;
struct Point
{
int x,y;
Point(){}
Point(int _x,int _y)
{
x = _x;y = _y;
}
Point operator -(const Point &b)const
{
return Point(x - b.x,y - b.y);
}
int operator *(const Point &b)const
{
return x*b.x + y*b.y;
}
int operator ^(const Point &b)const
{
return x*b.y - y*b.x;
}
};
struct Line
{
Point s,e;
Line(){}
Line(Point _s,Point _e)
{
s = _s;e = _e;
}
}; int xmult(Point p0,Point p1,Point p2) //计算p0p1 X p0p2
{
return (p1-p0)^(p2-p0);
}
const int MAXN = ;
Line line[MAXN];
int ans[MAXN];
int main(void)
{
int n,m,x1,y1,x2,y2,i;
int ui,li;
int cnt = ;
while(scanf("%d",&n),n)
{
if(cnt == ) cnt = ;
else printf("\n");
scanf("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2);
for(i = ; i < n; i++)
{
scanf("%d%d",&ui,&li);
line[i] = Line(Point(ui,y1),Point(li,y2));
}
line[n] = Line(Point(x2,y1),Point(x2,y2)); int x,y;
Point p;
memset(ans,,sizeof(ans)); while(m--)
{
scanf("%d %d",&x,&y);
p = Point(x,y);
int l = ,r = n,tmp = ;
while(l <= r)
{
int mid = (l + r)/;
if(xmult(p,line[mid].s,line[mid].e) < )
{
tmp = mid;
r = mid - ;
}
else
l = mid + ;
}
ans[tmp]++;
}
for(i = ; i <= n; i++)
printf("%d: %d\n",i,ans[i]);
}
return ;
}
最新文章
- FlumeNG 笔记
- COUNT(1)和COUNT(*)区别
- Atitit. 获取cpu占有率的 java c# .net php node.js的实现
- SQL中的取整函数FLOOR、ROUND、CEIL、TRUNC、SIGN
- C#/C++ 中字节数组与int类型转换
- jQuery使用之(五)处理页面的事件
- mysql5.7.9 源码安装 (转)
- Python学习_数据排序方法
- iOS:由URL成员UIImage
- C# ExcelHelper
- MySQL数据库操作类(PHP实现,支持连贯操作)
- Python模拟ICMP包
- 写入MySQL报错超出 max_allowed_packet 的问题
- BizTalk RosettaNet 开发笔记
- python(31)——【sys模块】【json模块 &; pickle模块】
- Linux命令Find实例
- vivado 调用UE
- Jenkins+Github配置【转】
- js便签笔记(4)——简单说说getAttributeNode()和setAttributeNode()
- 基于jQuery商品分类选择提交表单代码