M_sea

洛谷1355 神秘大三角
题目描述判断一个点与已知三角形的位置关系。若点在三角形内(不含边界),输出1;若点在三角形外(不含边界),输出2;...
扫描右侧二维码阅读全文
05
2017/09

洛谷1355 神秘大三角

题目描述

判断一个点与已知三角形的位置关系。

若点在三角形内(不含边界),输出1;

若点在三角形外(不含边界),输出2;

若点在三角形边界上(不含顶点),输出3;

若点在三角形顶点上,输出4。

传送门

算法

本题唯一的难点在于判断位置关系(这不就是答案吗。。。),但是不难想到方法——利用面积

具体说来,设输入的三角形为△ABC,要判断的点为D。
那么计算出S△ABD、S△ACD、S△BCD和S△ABC。
然后判断S△ABD+S△ACD+S△BCD与S△ABC的关系即可。

在具体一点,对应到原题的输出:

  1. 在三角形内,则S△ABD+S△ACD+S△BCD=S△ABC;
  2. 在三角形外,则S△ABD+S△ACD+S△BCD>S△ABC;
  3. 在三角形边界上,则S△ABD、S△ACD、S△BCD必有一个是0;
  4. 在顶点上,直接判坐标。

还有一点是判断顺序:先判4,再判2,然后是3和1。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int x[5],y[5]; //坐标
double dis(int x1,int y1,int x2,int y2) //计算(x2,y1)和(x2,y2)的欧几里得距离
{
    double x=abs(x1-x2),y=abs(y1-y2);
    return sqrt(x*x+y*y);
}
double S(int a,int b,int x,int y,int n,int m) //计算S△(a,b)(x,y)(n,m)
{
    double p,ab,ac,bc;
    ab=dis(a,b,x,y);
    ac=dis(a,b,n,m);
    bc=dis(x,y,n,m);
    p=(ab+ac+bc)/2;
    return sqrt(p*(p-ab)*(p-ac)*(p-bc));
}
int main()
{
    char ch;
    for (int i=1;i<=4;i++) cin>>ch>>x[i]>>ch>>y[i]>>ch; //输入
    for (int i=1;i<=3;i++)
    {
        if(x[i]==x[4]&&y[i]==y[4]) //判点重合
        {
            printf("4\n");
            return 0;
        }
    }
    int abc=(int)S(x[1],y[1],x[2],y[2],x[3],y[3])*100; //计算一堆面积,*100以解决精度
    int acd=(int)S(x[1],y[1],x[3],y[3],x[4],y[4])*100;
    int abd=(int)S(x[1],y[1],x[2],y[2],x[4],y[4])*100;
    int bcd=(int)S(x[2],y[2],x[3],y[3],x[4],y[4])*100;
    if (acd+abd+bcd>abc) //判2
    {
        printf("2\n");
        return 0;
    }
    else
    {
        if (!abd||!acd||!bcd) //判3
        {
            printf("3\n");
            return 0;
        }
        printf("1\n"); //否则就是1
    }
    return 0;
}

附言

既然是洛谷上很少的计算几何题,那当然要做一下啊。

最后修改:2018 年 11 月 09 日 04 : 02 PM

发表评论