poj2398Toy Storage
10283 ワード
http://poj.org/problem?id=2398
2318と同じデータがまだ少ない直接列挙2318は二分叉積で左右を判断した.
View Code
2318と同じデータがまだ少ない直接列挙2318は二分叉積で左右を判断した.
1 #include <iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<iostream>
5 #include<stdlib.h>
6 #include<algorithm>
7 #include<cmath>
8 using namespace std;
9 struct pointt
10 {
11 double x1,x2,mi,ma;
12 }p[1010];
13 int num[1010],co[1010];
14 bool cmp(pointt a,pointt b)
15 {
16 if(a.ma==b.ma)
17 return a.mi<b.mi;
18 return a.ma<b.ma;
19 }
20 int cross(pointt a,pointt b)
21 {
22 if((a.x1*b.x2-a.x2*b.x1)>0)
23 return 1;
24 return 0;
25 }
26 int main()
27 {
28 int i,j,k,n,m;
29 double x1,y1,x2,y2,x,y;
30 while(cin>>n)
31 {
32 if(n==0)
33 break;
34 memset(num,0,sizeof(num));
35 memset(co,0,sizeof(co));
36 cin>>m;
37 cin>>x1>>y1>>x2>>y2;
38 for(i = 1; i <= n ; i++)
39 {
40 cin>>p[i].x1>>p[i].x2;
41 p[i].ma = max(p[i].x1,p[i].x2);
42 p[i].mi = max(p[i].x1,p[i].x2);
43 }
44 p[n+1].x1 = x2;
45 p[n+1].x2 = x2;
46 p[n+1].ma = p[n+1].mi = x2;
47 sort(p,p+n+2,cmp);
48 for(i = 1; i <= m ; i++)
49 {
50 cin>>x>>y;
51 for(j = 1 ; j <= n+1 ; j++)
52 {
53 pointt a,b;
54 a.x1 = p[j].x1-p[j].x2;
55 a.x2 = y1-y2;
56 b.x1 = x-p[j].x2;
57 b.x2 = y-y2;
58 if(cross(a,b))
59 {
60 num[j]++;
61 break;
62 }
63 }
64 }
65 cout<<"Box
";
66 for(j = 1 ; j <= n+1 ;j++)
67 if(num[j])
68 co[num[j]]++;
69 for(j = 1 ; j <= n+1 ;j++)
70 {
71 if(co[j])
72 cout<<j<<": "<<co[j]<<endl;
73 }
74 }
75 return 0;
76 }
View Code