(叉积)B - Toy Storage POJ - 2398

时间:2021-08-21 11:32:54

题目链接:https://cn.vjudge.net/contest/276358#problem/B

题目大意:和上一次写叉积的题目一样,就只是线不是按照顺序给的,是乱序的,然后输出的时候是按照有三个点的区域有多少个---这个类型出发的。

AC代码:

 1 #include<iostream>
 2 #include<cstring>
 3 #include<string>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<stdio.h>
 7 #include<map>
 8 using namespace std;
 9 # define ll long long
10 const double PI = acos(-1.0);
11 const int maxn = 1e3+100;
12 map<int,int>vis;
13 int ans[maxn];
14 struct node
15 {
16     int u;
17     int l;
18 } q[maxn];
19 bool cmp(node t1,node t2)
20 {
21     return t1.u<t2.u;
22 }
23 int cal(int x2,int y2,int x1,int y1)//日常沙雕,这里一开始竟然打成了bool型,结果调试了将近两个小时。,。。
24 {
25     return (x1*y2)-(x2*y1);
26 }
27 bool cmp1(int t1,int t2)
28 {
29     return t1>t2;
30 }
31 int main()
32 {
33     int n,m;
34     int x1,y1,x2,y2;
35     while(scanf("%d",&n))
36     {
37         if(n==0)
38             break;
39         vis.clear();
40         memset(ans,0,sizeof(ans));
41         scanf("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2);
42         for(int i=0; i<n; i++)
43         {
44             scanf("%d %d",&q[i].u,&q[i].l);
45         }
46 
47         int x,y;
48         sort(q,q+n,cmp);
49         for(int i=1; i<=m; i++)
50         {
51             scanf("%d %d",&x,&y);
52             int j;
53             for( j=0; j<n; j++)
54             {
55                 if(cal(q[j].u-q[j].l,y1-y2,x-q[j].l,y-y2)<=0)
56                     break;
57             }
58             ans[j]++;
59         }
60         printf("Box\n");
61 //        for(int i=0;i<=n;i++){
62 //        printf("%d %d\n",i,ans[i]);
63 //        }
64         for(int i=0; i<=1000; i++)
65         {
66             vis[ans[i]]++;
67         }
68         for(int i=1; i<=1000; i++)
69         {
70             if(vis[i]==0)
71                 continue;
72             printf("%d: %d\n",i,vis[i]);
73         }
74     }
75     return 0;
76 }