计算几何题目入门-8月6号讲解

男娘i 2022-09-25 03:23 168阅读 0赞

计算几何入门题目

1. nefu 919 最最难的题：[http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem\_id=919][http_acm.nefu.edu.cn_JudgeOnline_problemShow.php_problem_id_919]

题面描述：

### 最最难的题 ###

#### Problem:919 ####

#### Time Limit:1000ms ####

#### Memory Limit:65536K ####

### Description ###

什么是最最难的题呢，当然就是计算三角形的面积啦，像我们这样皇家林业大学的ACMer们，AC这样的问题简直ius浪费生命，
    不过也没办法，上面有命令在先，出题一定要水，唉。你们就将就着做吧...

### Input ###

输入数据第一行是一个整数n，表示有n组测试实例，接下来有n行，每行6个数，分别表示三角形三个顶点的坐标x1，y1，x2，y2，x3，y3；
    （输入保证三个点不共线）

### Output ###

对于每组坐标，输出由这三个顶点构成的三角形的面积，结果保留两位小数。每组输出占一行。

### Sample Input ###

1
    0 0 1 0 0 1

### Sample Output ###

0.50

题目描述：

求解三角形的面积，叉积直接计算即可。

代码实现：

#include <iostream>
    	#include <stdio.h>
    	#include <math.h>
    	using namespace std;
    	 
    	typedef struct node
    	{
    	double x,y;
    	}point;
    	point p[5];
    	double cross(point a,point b)
    	{
    	return (a.x-p[0].x)*(b.y-p[0].y)-(a.y-p[0].y)*(b.x-p[0].x);
    	}
    	double s()
    	{
    	for(int i=0;i<3;i++)
    	{
    	scanf("%lf%lf",&p[i].x,&p[i].y);
    	}
    	double sum=0.0;
    	for(int i=1;i<2;i++)
    	{
    	sum+=cross(p[i],p[i+1]);
    	}return fabs(sum);
    	}
    	int main()
    	{
    	int n1;
    	double sum1;
    	while(cin>>n1)
    	{
    	for(int j=0;j<n1;j++)
    	{
    	sum1=s();
    	printf("%.2lf\n",sum1/2.0);
    	}
    	}
    	return 0;
    	}

nefu920：[http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem\_id=920][http_acm.nefu.edu.cn_JudgeOnline_problemShow.php_problem_id_920]

关于种地的忧伤故事

题面描述：

### 关于种地的忧伤故事 ###

#### Problem:920 ####

#### Time Limit:1000ms ####

#### Memory Limit:65536K ####

### Description ###

“ 改革春风吹满地,
    不会AC没关系;
    实在不行回老家，
    还有一亩三分地。
    谢谢!（乐队奏乐）”
    
    话说部分学生心态极好，每天就知道游戏，寒假集训如此简单的题目，也是云里雾里，而且，还竟然来这么几句打油诗。
    
    好呀，学长的责任就是帮你解决问题，既然想种田，那就分你一块。
    
    这块田位于黑龙江省NEFU大学皇家帽儿山林场，多边形形状的一块地，原本是荣大小姐的，现在就准备送给你了。
    
    不过，任何事情都没有那么简单，你必须首先告诉我这块地到底有多少面积，如果回答正确才能真正得到这块地。
    
    发愁了吧？就是要让你知道，种地也是需要AC知识的！以后还是好好练吧...

### Input ###

输入数据包含多个测试实例，每个测试实例占一行，每行的开始是一个整数n(3<=n<=100)，它表示多边形的边数（当然也是顶点数），
    
    然后是按照逆时针顺序给出的n个顶点的坐标（x1, y1, x2, y2... xn, yn）,为了简化问题，这里的所有坐标都用整数表示。
    
    输入数据中所有的整数都在32位整数范围内，n=0表示数据的结束，不做处理。

### Output ###

对于每个测试实例，请输出对应的多边形面积，结果精确到小数点后一位小数。
    每个实例的输出占一行。

### Sample Input ###

3 0 0 1 0 0 1
    4 1 0 0 1 -1 0 0 -1
    0

### Sample Output ###

0.5
    2.0

题目大意：求解多边形的面积，利用叉积直接累加求和，最后求绝对值。

代码实现：

#include <iostream>
    #include <stdio.h>
    #include <math.h>
    using namespace std;
     
    typedef struct node
    {
        double x,y;
    }point;
    point p[105];
    double cross(point a,point b)
    {
        return (a.x-p[0].x)*(b.y-p[0].y)-(a.y-p[0].y)*(b.x-p[0].x);
    }
    double s(int n)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        double sum=0.0;
        for(int i=1;i<n-1;i++)
        {
            sum+=cross(p[i],p[i+1]);
        }return fabs(sum);
    }
    int main()
    {
        int n1;
        double sum1;
        while(cin>>n1)
        {
            if(n1==0) break;
            sum1=s(n1);
            printf("%.1lf\n",sum1/2.0);
        }
        return 0;
    }

3.nefu922线段相交： [http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem\_id=922][http_acm.nefu.edu.cn_JudgeOnline_problemShow.php_problem_id_922]

题面描述：

### 线段相交 ###

#### Problem:922 ####

#### Time Limit:1000ms ####

#### Memory Limit:65536K ####

### Description ###

课件中屌丝学长关于线段相交可是讲的很清楚很彻底了，这道线段相交的水题就当做是下道题的铺垫吧。

### Input ###

输入数据有多组，每组第一行有一个整数n，表示测试实例的数目，接下来有n行，每行8个数，分别表示2条线段的起点和终点：
    线段1：（x1,y1）(x2,y2)
    线段2： (x3,y3) (x4,y4)
    n=0表示输入结束，该组不做任何处理。

### Output ###

你的任务就是，对于每组输入，判断他们是否相交。相交输出“YES”，否则输出“no”；

### Sample Input ###

2
    0 0 0 1 1 0 1 1
    0 0 0 1 0 0 0 1
    0

### Sample Output ###

no
    YES

题目大意：

判断两条线段是否相交，快速排斥加跨立实验。

代码实现：

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    double max(double a,double b)
    {
        return a>b?a:b;
    }
    
    double min(double a,double b)
    {
        return a<b?a:b;
    }
    
    struct point
    {
        double x;
        double y;
    };
    
    struct V
    {
        point sstart;
        point eend;
    };
    
    double multi(point p1,point p2,point p0)
    {
        return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
    }
    
    int across(V v1,V v2)
    {
        if(max(v1.sstart.x,v1.eend.x)>=min(v2.sstart.x,v2.eend.x)&&
           max(v2.sstart.x,v2.eend.x)>=min(v1.sstart.x,v1.eend.x)&&
           max(v1.sstart.y,v1.eend.y)>=min(v2.sstart.y,v2.eend.y)&&
           multi(v2.sstart,v1.eend,v1.sstart)*multi(v1.eend,v2.eend,v1.sstart)>=0&&
           multi(v1.sstart,v2.eend,v2.sstart)*multi(v2.eend,v1.eend,v2.sstart)>=0)
            return 1;
        else return 0;
    }
    
    int main()
    {
        int n;
        int flag;
        V v1,v2;
        while(scanf("%d",&n)!=EOF)
        {
            if(n==0)
                break;
            while(n--)
            {
                flag=0;
                scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&v1.sstart.x,&v1.sstart.y,&v1.eend.x,&v1.eend.y,
                      &v2.sstart.x,&v2.sstart.y,&v2.eend.x,&v2.eend.y);
                flag=across(v1,v2);
                //cout<<"flag="<<flag<<endl;
                if(flag)
                {
                    printf("YES\n");
                }
                else
                {
                    printf("no\n");
                }
            }
        }
        return 0;
    }

4.hdu2036改革春风吹满地：[http://acm.hdu.edu.cn/showproblem.php?pid=2036][http_acm.hdu.edu.cn_showproblem.php_pid_2036]

题面描述：

# 改革春风吹满地 #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 30031 Accepted Submission(s): 15474**

Problem Description

“ 改革春风吹满地,  
不会AC没关系;  
实在不行回老家，  
还有一亩三分地。  
谢谢!（乐队奏乐）”  
  
话说部分学生心态极好，每天就知道游戏，这次考试如此简单的题目，也是云里雾里，而且，还竟然来这么几句打油诗。  
好呀，老师的责任就是帮你解决问题，既然想种田，那就分你一块。  
这块田位于浙江省温州市苍南县灵溪镇林家铺子村，多边形形状的一块地，原本是linle 的，现在就准备送给你了。不过，任何事情都没有那么简单，你必须首先告诉我这块地到底有多少面积，如果回答正确才能真正得到这块地。  
发愁了吧？就是要让你知道，种地也是需要AC知识的！以后还是好好练吧...

Input

输入数据包含多个测试实例，每个测试实例占一行，每行的开始是一个整数n(3<=n<=100)，它表示多边形的边数（当然也是顶点数），然后是按照逆时针顺序给出的n个顶点的坐标（x1, y1, x2, y2... xn, yn）,为了简化问题，这里的所有坐标都用整数表示。  
输入数据中所有的整数都在32位整数范围内，n=0表示数据的结束，不做处理。

Output

对于每个测试实例，请输出对应的多边形面积，结果精确到小数点后一位小数。  
每个实例的输出占一行。

Sample Input

3 0 0 1 0 0 1
    4 1 0 0 1 -1 0 0 -1
    0

Sample Output

0.5
    2.0

题目大意：

求解多边形的面积，叉积。

代码实现：

#include <cstdio>
    #include <cmath>
    #include <bits/stdc++.h>
    
    using namespace std;
    
    struct TPoint
    {
        long long x,y;
        TPoint(){}
        TPoint(long long xx,long long yy)
        {
            x=xx;
            y=yy;
        }
        TPoint operator - (TPoint&b)const
        {
            return TPoint(x-b.x,y-b.y);
        }
    };
    TPoint data[100];
    
    double cross(TPoint A,TPoint B)
    {
        return A.x*B.y-A.y*B.x;
    }
    
    double poly_are(TPoint p[],int n)
    {
        double ans=0.0;
        for(int i=1;i<n-1;i++) ///共计算了n-2次
        {
            ans+=cross(p[i]-p[0],p[i+1]-p[0]);
        }
        return fabs(ans)/2.0;
    }
    
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            if(n==0)
                break;
            for( int i=0;i<n;i++)
            {
                scanf("%lld%lld",&data[i].x,&data[i].y);
            }
            printf("%.1lf\n",poly_are(data,n));
        }
        return 0;
    }

5.poj1654 Area：[http://poj.org/problem?id=1654][http_poj.org_problem_id_1654]

题面描述：

Area

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;19122</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;5249</td> 
  </tr> 
 </tbody> 
</table>

Description

You are going to compute the area of a special kind of polygon. One vertex of the polygon is the origin of the orthogonal coordinate system. From this vertex, you may go step by step to the following vertexes of the polygon until back to the initial vertex. For each step you may go North, West, South or East with step length of 1 unit, or go Northwest, Northeast, Southwest or Southeast with step length of square root of 2.  
  
For example, this is a legal polygon to be computed and its area is 2.5:  
![1654_1.jpg][]

Input

The first line of input is an integer t (1 <= t <= 20), the number of the test polygons. Each of the following lines contains a string composed of digits 1-9 describing how the polygon is formed by walking from the origin. Here 8, 2, 6 and 4 represent North, South, East and West, while 9, 7, 3 and 1 denote Northeast, Northwest, Southeast and Southwest respectively. Number 5 only appears at the end of the sequence indicating the stop of walking. You may assume that the input polygon is valid which means that the endpoint is always the start point and the sides of the polygon are not cross to each other.Each line may contain up to 1000000 digits.

Output

For each polygon, print its area on a single line.

Sample Input

4
    5
    825
    6725
    6244865

Sample Output

0
    0
    0.5
    2

题目大意：

求解多边形的面积，但是要注意细节问题。

算法实现时，注意：此题一定要用\_\_int64来代替long long，且中间过程不必把每一个点都记录下来，放在数组里，最后再进行计算面积，而是在中间得到点的坐标的过程中，就进行面积的计算，利用的是叉乘，且对于\_\_int64类型的数并不能通过fabs()或者abs()数学函数直接进行求绝对值，所以，只需要判断一下正负，负数则取相反数即可。

代码实现：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    char str[1000100];
    
    int movedata(int n, __int64 &x, __int64 &y)
    {
        int flag=0;
        switch(n)
        {
        case 1:
            x=x-1;
            y=y-1;
            flag=1;
            break;
        case 2:
            y=y-1;
            flag=1;
            break;
        case 3:
            x=x+1;
            y=y-1;
            flag=1;
            break;
        case 4:
            x=x-1;
            flag=1;
            break;
        case 6:
            x=x+1;
            flag=1;
            break;
        case 7:
            x=x-1;
            y=y+1;
            flag=1;
            break;
        case 8:
            y=y+1;
            flag=1;
            break;
        case 9:
            x=x+1;
            y=y+1;
            flag=1;
            break;
        default :
            break;
        }
        if(flag)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    
    int main()
    {
        int t,flag;
        __int64 xx,yy,area;
        __int64 x1,y1;
        scanf("%d",&t);
        while(t--)
        {
            memset(str,0,sizeof(str));
            xx=0;
            yy=0;
            area=0;
            flag=0;
            scanf("%s",str);
            int len=strlen(str);
            for(int i=0; i<len; i++)
            {
                flag=movedata(str[i]-'0',xx,yy);
                if(i>=1)
                {
                    if(flag)
                    {
                        area+=x1*yy-xx*y1;
                        x1=xx;
                        y1=yy;
                    }
                    else
                    {
                        break;
                    }
                }
                else
                {
                    x1=xx;
                    y1=yy;
                }
            }
            if(x1==0&&y1==0)
            {
                if(area<0)
                    area=-area;
                if(area%2)
                {
                    printf("%I64d",area/2);
                    printf(".5\n");
                }
                else
                {
                    printf("%I64d\n",area/2);
                }
            }
            else
            {
                printf("0\n");
            }
        }
        return 0;
    }

6.hdu1174爆头： [http://acm.hdu.edu.cn/showproblem.php?pid=1174][http_acm.hdu.edu.cn_showproblem.php_pid_1174]

题目描述：

# 爆头 #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 2323 Accepted Submission(s): 1037**

Problem Description

gameboy是一个CS高手，他最喜欢的就是扮演警察，手持M4爆土匪的头。也许这里有人没玩过CS，有必要介绍一下“爆头”这个术语：所谓爆头，就是子弹直接命中对方的头部，以秒杀敌人。  
  
现在用一个三维的直角坐标系来描述游戏中的三维空间（水平面为xoy平面，z轴正方向是上方）。假设游戏中角色的头是一个标准的球。告诉你土匪的身高，头部半径，所站位置的坐标；gameboy所控警察的身高，头部半径，所站位置的坐标，以及枪头所指方向的单位向量。gameboy所控警察所握的是M4，抢瞄准时枪膛中的子弹跟视线基本同线，我们忽略它们的距离，就当成同线。由于土匪手持AK47,所以他是很嚣张地正立着。而警察手持M4，正在瞄准，由于瞄准时身体微弯，视线从头心出发，他头部的实际高度比正立时低10%。  
  
你的任务就是，计算gameboy在这一刻扣下扳机，能否爆土匪的头。注意：这里忽略子弹的直径和重力作用，也就是说子弹是无限小的，弹道是一条笔直的射线，警察与土匪间没有障碍物。并且只要子弹擦到头部，哪怕是边缘，也算爆头。

Input

测试数据的第一行有一个正整数T，表示有T组测试数据。每组数据的第一行有五个实数，h1,r1,x1,y1,z1，分别表示土匪的身高，头部半径以及所站的位置。第二行有八个实数，h2,r2,x2,y2,z2,x3,y3,z3，分别表示警察的身高，头部半径，所站位置，以及枪头所指方向的方向向量。

Output

每一组输入数据对应一行输出。如果能爆土匪的头，输出"YES",否则输出"NO"。

Sample Input

2
    1.62 0.1 10.0 10.0 10.0
    1.80 0.09 0.0 0.0 0.0 1.0 1.0 1.0
    1.62 0.1 0.0 0.0 0.0
    1.80 0.09 10.0 10.0 10.0 -1.0 -1.0 -1.0

Sample Output

YES
    YES

题目大意：

题目具有很强的迷惑性，但其实就是：

利用叉乘求点到直线（向量的距离），三维空间中的叉乘，借助于三阶的行列式。

代码实现：

#include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    int main()
    {
        double h1,r1,x1,y1,z1,h2,r2,x2,y2,z2,x3,y3,z3;
        int t;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%lf%lf%lf%lf%lf",&h1,&r1,&x1,&y1,&z1);
            scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&h2,&r2,&x2,&y2,&z2,&x3,&y3,&z3);
            double k1=z1+h1-r1;///土匪的纵坐标
            double k2=z2+0.9*h2-r2;///警察的纵坐标
            double a=x1-x2;
            double b=y1-y2;
            double c=k1-k2;///警察头心和土匪头心的连线
            double a1=b*z3-c*y3;
            double b1=c*x3-a*z3;
            double c1=a*y3-b*x3;///连线和枪向量的叉乘
            double d=(a1*a1+b1*b1+c1*c1)/(x3*x3+y3*y3+z3*z3);///表示土匪头心距离枪向量的距离的平方
            if(d<=r1*r1&&(a*x3+b*y3+c*z3>0))///确保枪向量的方向是指向土匪的
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
        return 0;
    }

关于凸包的问题详见上一篇博客~

[http_acm.nefu.edu.cn_JudgeOnline_problemShow.php_problem_id_919]: http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=919
[http_acm.nefu.edu.cn_JudgeOnline_problemShow.php_problem_id_920]: http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=920
[http_acm.nefu.edu.cn_JudgeOnline_problemShow.php_problem_id_922]: http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=922
[http_acm.hdu.edu.cn_showproblem.php_pid_2036]: http://acm.hdu.edu.cn/showproblem.php?pid=2036
[http_poj.org_problem_id_1654]: http://poj.org/problem?id=1654
[1654_1.jpg]: /images/20220718/f04e8fa935ba4094afb2e84824656565.png
[http_acm.hdu.edu.cn_showproblem.php_pid_1174]: http://acm.hdu.edu.cn/showproblem.php?pid=1174