Moon Game(fzu2148)&&凸四边形

题目链接

这道题花费了一下午的时间,其中遇到了n多问题
题目大意:给你n的点的坐标,求可以组成多少个凸四边形
解这道题首先要会判别凸四边形

图中abcd为凹四边形,a1bcd位凸四边形,可以发现在凹四边形中三角形abd加abc加acd的面积之和等于dbc的面积,而凸三角形不满足这一条件,因此可以用这个方法来判断

第二个问题是三角形面积的求法,在已知点得坐标的情况先可以先用勾股定理求出每条边的长度,然后应用海伦定理,

即p=(a+b+c)/2;

s=sqrt(p*(p-a)*(p-b)*(p-c));

本以为这样就能A了,结果。。。TLE!

后来发现是勾股定理求边长时使用的pow函数(计算平方)耗时太高,改为两数相乘后仅耗费了500毫秒,效率提升了一倍多。

代码

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
struct node
{
    int x,y;
}a[33];
bool cmp(node a,node b)
{
    if(a.x==b.x)
    {
        return a.y<b.y;
    }
    return a.x<b.x;
}

double s(int da,int db,int dc)
{
    double la,lb,lc,p;
    la=sqrt((a[db].x-a[dc].x)*(a[db].x-a[dc].x)*1.0+(a[db].y-a[dc].y)*(a[db].y-a[dc].y)*1.0);
    lb=sqrt((a[da].x-a[dc].x)*(a[da].x-a[dc].x)*1.0+(a[da].y-a[dc].y)*(a[da].y-a[dc].y)*1.0);
    lc=sqrt((a[db].x-a[da].x)*(a[db].x-a[da].x)*1.0+(a[db].y-a[da].y)*(a[db].y-a[da].y)*1.0);
    p=(la+lb+lc)/2;
    return sqrt(p*(p-la)*(p-lb)*(p-lc));
}

int f(int da,int db,int dc,int dd)
{
//    cout<<da<<" "<<db<<" "<<dc<<" "<<dd<<endl;
//    cout<<s(da,db,dc)+s(da,db,dd)+s(da,dd,dc)<<" "<<s(db,dc,dd)<<endl;
    if(s(da,db,dc)+s(da,db,dd)+s(da,dd,dc)-s(db,dc,dd)<0.01)
    {
        return 0;
    }
    else return 1;
}

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    int n;
    for(int kk=1;kk<=t;kk++)
    {
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>a[i].x>>a[i].y;
        }
        //sort(a,a+n,cmp);
        int sum=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                for(int k=j+1;k<n;k++)
                {
                    for(int l=k+1;l<n;l++)
                    {
                        if(f(i,j,k,l)&&f(j,i,k,l)&&f(k,i,j,l)&&f(l,i,j,k))
                        {
                            sum++;
                        }
                    }
                }
            }
        }
        cout<<"Case "<<kk<<": "<<sum<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注