Fork me on GitHub

POJ 2398 Toy Storage(计算几何)

题目

描述略,此题和 POJ 2318 基本是类似的,只不过最后统计的是每个分区内的玩具个数有几个,还有坑点就是题目输入的数据不像 POJ 2318 的数据是按照点的坐标和线段端点点的坐标从左到右依次输入,而是乱输入的,因此需要建立结构体将其排序。给出 POJ 2318的题解 ,这道题只需注意以上两个坑点就很容易了,再给出这道题的代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int N = 50001;
int n,m;
int u[N],l[N];
int ans[N],an[N],bn[N];
int x1,x2,y1,y2;
struct point
{
int x,y;
}a[N];
struct line
{
int u,v;
}b[N];
bool cmp1(point a,point b)
{
return a.x<b.x;
}
bool cmp2(line c,line d)
{
return c.u<d.u;
}
int xmul(int x1,int y1,int x2,int y2)
{
return (x1*y2)-(x2*y1);
}
int main()
{
while(cin>>n,n)
{
cin>>m>>x1>>y1>>x2>>y2;
for(int i=0;i<n;i++)
{
cin>>b[i].u>>b[i].v;
ans[i]=0;
}
ans[n]=0;
sort(b,b+n,cmp2);
for(int i=0;i<m;i++)
{
cin>>a[i].x>>a[i].y;
}
sort(a,a+m,cmp1);
for(int i=0,j;i<m;i++)
{
for(j=0;j<n;j++)
if(xmul(a[i].x-b[j].v,a[i].y-y2,b[j].u-b[j].v,y1-y2)<=0)
break;
++ans[j];
}
for(int i = 1;i <= n;i++)
an[i] = 0;
for(int i = 0;i <= n;i++)
if(ans[i]>0)
an[ans[i]]++;
printf("Box\n");
for(int i = 1;i <= n;i++)
if(an[i]>0)
printf("%d: %d\n",i,an[i]);
}
return 0;
}
-------------本文结束感谢您的阅读-------------
obsidian wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持是我最大的动力!