Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://poj.org/problem?id=2398
题意大概是说将一个盒子用n个board分成n+1 部分
然后往里面放toy,给定盒子,board,和toy的坐标
问所有的toy放完后,有多少部分中有t个toy;
简单计算几何
需要判断的是点和直线的关系.
判断 某一点在直线左右侧
左右方向是相对前进方向的,只要指定了前进方向就可以知道左右(比如指定前进方向是从直线的起点到终点).判断点在直线的左侧还是右侧是计算几何里面的一个最基本算法.使用矢量来判断. 定义：平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量：
** S(P1,P2,P3)=|y1 y2 y3|= (x1-x3)(y2-y3)-(y1-y3)(x2-x3)
当P1P2P3逆时针时S为正的，当P1P2P3顺时针时S为负的。
令矢量的起点为A，终点为B，判断的点为C， 如果S（A，B，C）为正数，则C在矢量AB的左侧； 如果S（A，B，C）为负数，则C在矢量AB的右侧； 如果S（A，B，C）为0，则C在直线AB上。**
1
2
3
4
5
6 /*************************************************************************
7 > File Name: code/poj/2398.cpp
8 > Author: 111qqz
9 > Email: rkz2013@126.com
10 > Created Time: 2015年11月08日 星期日 10时04分32秒
11 ************************************************************************/
12 #include<iostream>
13 #include<iomanip>
14 #include<cstdio>
15 #include<algorithm>
16 #include<cmath>
17 #include<cstring>
18 #include<string>
19 #include<map>
20 #include<set>
21 #include<queue>
22 #include<vector>
23 #include<stack>
24 using namespace std;
25 #define REP(i, n) for (int i=0;i<int(n);++i)
26 typedef long long LL;
27 typedef unsigned long long ULL;
28 const int N=2E3+5;
29 struct node
30 {
31 int x,y;
32 };
33 struct node rec,rec2;
34 struct node par[N],par2[N];
35 struct node toy[N];
36 int ans[N],cnt[N];
37 int n,m;
38 bool judge(node p1,node p2,node p3) //判断点是否在直线的[右侧!!]
39 {
40 int s = (p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x);
41 if (s>0) return false;
42 if (s<0) return true;
43 }
44 bool cmp(node a,node b)
45 {
46 if (a.x<b.x) return true;
47 if (a.x==b.x&&a.y<b.y) return true;
48 return false;
49 }
50 int main()
51 {
52 // freopen("in.txt","r",stdin);
53 while (scanf("%d",&n)!=EOF&&n)
54 {
55 memset(ans,0,sizeof(ans));
56 memset(par,0,sizeof(par));
57 memset(par2,0,sizeof(par2));
58 memset(toy,0,sizeof(toy));
59 cin>>m>>rec.x>>rec.y>>rec2.x>>rec2.y;
60 for ( int i = 1 ; i <= n ; i++)
61 {
62 cin>>par[i].x>>par2[i].x;
63 par[i].y=rec.y;
64 par2[i].y=rec2.y;
65 }
66 for ( int i = 1 ; i <= n-1 ; i++)
67 {
68 for ( int j = i+1 ; j <= n ; j++)
69 {
70 if (par[i].x>par[j].x)
71 {
72 swap(par[i].x,par[j].x);
73 // swap(par[i].y,par[j].y);
74 swap(par2[i].x,par2[j].x);
75 // swap(par2[i].y,par2[j].y);
76 }
77 }
78 }
79 // for ( int i = 1 ; i <= n ; i++)
80 // cout<<par[i].x<<endl;
81 for ( int i = 1 ; i <= m ; i++ )
82 {
83 cin>>toy[i].x>>toy[i].y;
84 }
85 int p;
86 sort(toy+1,toy+m+1,cmp); //如果第i个娃娃在第k个分划中,那么排序后第i+1个娃娃至少在第k个分划中....(某大神说过,顺手就能写的优化顺手
87 // for ( int i = 1 ; i <= m ; i++) cout<<"x[i]:"<<toy[i].x<<" y[i]:"<<toy[i].y<<endl;
88 for ( int i = 1 ; i <= m ; i++)
89 {
90 p = n + 1; //如果在所有board的右侧,那么一定是在最后一个分划中(n个板子形成n+1个分划)
91 bool ok=false;
92 for ( int j = 1 ; j <= n ; j++)
93 {
94 ok=judge(par2[j],par[j],toy[i]);
95 if (!ok)
96 {
97 // cout<<"i:"<<i<<" j:"<<j<<" "<<par2[j].x<<" "<<par2[j].y<<" "<<par[j].x<<" "<<par[j].y<<endl;
98 p = j;
99 break;
100 // cout<< "hhhhhh"<<"I:"<<i<<" j:"<<j<<endl;
101 }
102 }
103 ans[p]++;
104 }
105 cout<<"Box"<<endl;
106 memset(cnt,0,sizeof(cnt));
107 for ( int i = 1 ; i <= n+1 ; i++)
108 {
109 if (ans[i]==0) continue;
110 cnt[ans[i]]++;
111 // printf("%d: %d\n",i-1,ans[i]);
112 }
113 // puts("");
114 for ( int i = 1 ; i <= m ; i++)
115 {
116 if (cnt[i]==0) continue;
117 printf("%d: %d\n",i,cnt[i]);
118 }
119 }
120 return 0;
121 }