首页 > 代码库 > poj2398Toy Storage
poj2398Toy Storage
同poj2318!
1 //Accepted 220 KB 0 ms 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int MAXN = 1005; 7 struct node 8 { 9 double x,y; 10 node() 11 { 12 13 } 14 node(double x,double y):x(x),y(y) 15 { 16 17 } 18 struct node operator-(struct node t) 19 { 20 return node(x-t.x,y-t.y); 21 } 22 struct node operator+(struct node t) 23 { 24 return node(x+t.x,y+t.y); 25 } 26 double operator*(struct node t) 27 { 28 return x*t.y-y*t.x; 29 } 30 }; 31 struct line 32 { 33 struct node p1,p2; 34 }; 35 int cmp(struct line l1,struct line l2) 36 { 37 if (l1.p1.x-l2.p1.x<1e-9) 38 return 1; 39 return 0; 40 } 41 line L[MAXN]; 42 struct node query_node; 43 int n,m; 44 struct node up,lr; 45 int num[MAXN]; 46 struct count_node 47 { 48 int sid; 49 int count; 50 }f[MAXN]; 51 void build() 52 { 53 for (int i=0;i<=n;i++) 54 { 55 f[i].count=0; 56 f[i].sid=i; 57 } 58 } 59 int cmp2(count_node x,count_node y) 60 { 61 return x.count<y.count; 62 } 63 double judge(struct node p,struct line t) 64 { 65 return (t.p1-p)*(t.p2-p); 66 } 67 void read() 68 { 69 scanf("%d",&m); 70 scanf("%lf%lf%lf%lf",&up.x,&up.y,&lr.x,&lr.y); 71 for (int i=1;i<=n;i++) 72 { 73 scanf("%lf%lf",&L[i].p1.x,&L[i].p2.x); 74 L[i].p1.y=up.y; 75 L[i].p2.y=lr.y; 76 } 77 sort(L+1,L+n+1,cmp); 78 } 79 void slove() 80 { 81 memset(num,0,sizeof(num)); 82 for (int j=0;j<m;j++) 83 { 84 scanf("%lf%lf",&query_node.x,&query_node.y); 85 int i; 86 for (i=1;i<=n;i++) 87 { 88 if (judge(query_node,L[i])<1e-9) break; 89 } 90 num[i-1]++; 91 } 92 build(); 93 for (int i=0;i<=n;i++) 94 { 95 if (num[i]!=0) 96 f[num[i]].count++; 97 } 98 //sort(f,f+n+1,cmp2); 99 for (int i=0;i<=n;i++) 100 { 101 if (f[i].count!=0) 102 printf("%d: %d\n",f[i].sid,f[i].count); 103 } 104 } 105 int main() 106 { 107 while (scanf("%d",&n),n) 108 { 109 read(); 110 printf("Box\n"); 111 slove(); 112 } 113 return 0; 114 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。