计算几何的几道题

时间：2023-02-10 20:21:11

叉积求面积

hdu2036（模版题）:

http://acm.hdu.edu.cn/showproblem.php?pid=2036

计算几何的几道题计算几何的几道题View Code 
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 #include<math.h>
 5 using namespace std;
 6 struct node
 7 {
 8     int x,y;
 9 }q[101];
10 double cross(node a,node b)
11 {
12     return a.x*b.y-a.y*b.x;
13 }
14 int main()
15 {
16     int i,j,k,n;
17     while(scanf("%d",&n)&&n)
18     {
19         double s = 0;
20         for(i = 1; i <= n ; i++)
21         scanf("%d%d",&q[i].x,&q[i].y);
22         for(i = 1 ; i <= n ; i++)
23         {
24             if(i<n)
25             s+=cross(q[i],q[i+1]);
26             else
27             s+=cross(q[n],q[1]);
28         }
29         if(s<0)
30         s  = -s;
31         s = s/2;
32         printf("%.1lf\n",s);
33     }
34     return 0;
35 }

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=41

求怎样旋转这个半圆能包围最多的点

 

1. 到圆心的距离大于半径的点直接排除。
  
2. 以圆心和任意一点确定一 有向线段作为半径位置，分别计数该有向线段左边点的个数 (nl) 和右边点的个数 (nr) 。
 
重复步骤 2 直到所有点都被枚举
过。
4. 枚举过程中出现的最大的 nl 或
nr 就是所求的结果。
计算几何的几道题计算几何的几道题View Code 
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 using namespace std;
 5 struct node
 6 {
 7     int x,y;
 8 }no[200];
 9 int cross(int x1,int y1,int x2,int y2)
10 {
11     return x1*y2-x2*y1;
12 }
13 int main()
14 {
15     int i,j,k,n,m,x,y,g;
16     double r;
17     while(scanf("%d%d%lf",&n,&m,&r)!=EOF)
18     {
19         if(r<0)
20         break;
21         scanf("%d",&k);
22         g = 0;
23         for(i = 1; i <= k ;i++)
24         {
25             scanf("%d%d",&x,&y);
26             if((x-n)*(x-n)+(y-m)*(y-m)<=r*r)//排除到圆心距离大于半径的点
27             {
28                 g++;
29                 no[g].x = x;
30                 no[g].y = y;
31             }
32         }
33         int max = 0;
34         for(i = 1; i <= g ; i++)
35         {
36             int numl = 0,numr = 0;
37             for(j = 1; j <= g ; j++)
38             {
39                 int d = cross(no[i].x-n,no[i].y-m,no[j].x-n,no[j].y-m);//点乘判断是哪边的点
40                 if(d==0)
41                 {
42                     numl++;
43                     numr++;
44                 }
45                 if(d>0)
46                 numl++;
47                 if(d<0)
48                 numr++;
49             }
50             if(numl>max)
51             max = numl;
52             if(numr>max)
53             max = numr;
54         }
55         printf("%d\n",max);
56     }
57     return 0;
58 }
规范相交题目 利用差乘判断相交 不用考虑重点问题
计算几何的几道题计算几何的几道题View Code 
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 using namespace std;
 5 double eps=0.0000000001;
 6 struct node
 7 {
 8     double x1,x2,y1,y2;
 9 };
10 double cross(double x1,double x2,double y1,double y2)
11 {
12     return x1*y2-x2*y1;
13 }
14 int main()
15 {
16     int i,j,k,n,m;
17     node q[101];
18     while(scanf("%d",&n)&&n)
19     {
20         int num = 0;
21         for(i = 1; i <= n ; i++)
22         {
23             scanf("%lf%lf%lf%lf",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2);
24         }
25         for(i = 1; i < n; i++)
26         for(j = i+1 ; j <= n ; j++)
27         {
28             double d1 = cross(q[i].x1-q[i].x2,q[i].y1-q[i].y2,q[i].x1-q[j].x1,q[i].y1-q[j].y1);
29             double d2 = cross(q[i].x1-q[i].x2,q[i].y1-q[i].y2,q[i].x1-q[j].x2,q[i].y1-q[j].y2);
30             double d3 = cross(q[j].x1-q[j].x2,q[j].y1-q[j].y2,q[j].x1-q[i].x2,q[j].y1-q[i].y2);
31             double d4 = cross(q[j].x1-q[j].x2,q[j].y1-q[j].y2,q[j].x1-q[i].x1,q[j].y1-q[i].y1);
32             if(d1*d2<eps&&d3*d4<eps)
33             num++;
34         }
35         printf("%d\n",num);
36     }
37     return 0;
38 }

  http://poj.org/problem?id=2318

二分查找+点乘判断左右

计算几何的几道题计算几何的几道题View Code 
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<string.h>
 4 using namespace std;
 5 struct node
 6 {
 7     int x1,x2;
 8 }q[5001];
 9 int cross(node a,node b)
10 {
11     if(a.x1*b.x2-a.x2*b.x1>0)
12     return 1;
13     else
14     return 0;
15 }
16 int x1,x2,n,y1,y2;
17 int judge(int x,int y)
18 {
19     int l =0,r = n+1,mid,k;
20     node a,b;
21     while(l<r)
22     {
23         mid = (l+r)/2;
24         if(mid==l)
25         return mid;
26         a.x1 = q[mid].x1-q[mid].x2;
27         a.x2 = y1-y2;
28         b.x1 = x-q[mid].x2;
29         b.x2 = y-y2;
30         if(cross(a,b))
31         r = mid;
32         else
33         l = mid;
34     }
35     return mid;
36 }
37 int num[5010];
38 int main()
39 {
40     int i,j,m,t,x,y;
41     while(scanf("%d",&n)&&n)
42     {
43         memset(num,0,sizeof(num));
44         scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
45         for(i = 1; i <= n ; i++)
46         scanf("%d%d",&q[i].x1,&q[i].x2);
47         while(m--)
48         {
49             scanf("%d%d",&x,&y);
50             int k = judge(x,y);
51             num[k]++;
52         }
53         for(i = 0 ; i <= n ; i++)
54         printf("%d: %d\n",i,num[i]);
55         puts("");
56     }
57     return 0;
58 }

 

标签：

相关文章