https://vjudge.net/problem/FZU-2148
题目的大致意思就是给你n个点。让你计算这个点可以构成的凸四边形的个数。
看到一个超级厉害的解法。就是道理其实都懂可是我就是没想到。所以觉得他厉害吧。
对于一个凹四边形来说。把各个顶点相连。就会得到三个三角形。这三个三角形的面积加和就等于大三角形的面积。凸三角形就不行。自己画画就能想到了。
直接上代码吧。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
struct point{int x,y;
}arr[35];
double area(int a,int b,int c){return fabs(arr[b].x*arr[a].y-arr[c].x*arr[a].y-arr[a].x*arr[b].y+arr[c].x*arr[b].y+ arr[a].x*arr[c].y-arr[b].x*arr[c].y)/2;
}int judge(int a,int b,int c,int d){if(area(a,b,c)==(area(a,b,d)+area(a,c,d)+area(b,c,d))){return 0;}return 1;
}
int main(){int T;cin>>T;int kase=0;while(T--){memset(arr,0,sizeof(arr));int n;cin>>n;for(int i=0;i<n;i++){cin>>arr[i].x>>arr[i].y;}int ans=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(judge(i,j,k,l)&&judge(i,j,l,k)&&judge(j,l,k,i)&&judge(i,l,k,j)){ans++;}}}}}printf("Case %d: %d\n",++kase,ans);}return 0;
}关于那个三角形面积计算公式啊。
就是可以用三个点的坐标就可以求面积。
设A(x1,y1),B(x2,y2),C(x3,y3)
由A–>B–>C–>A 按逆时针方向转。(行列式书写要求）
设三角形的面积为S
则S=（1/2)*(下面行列式）
|x1 y1 1|
|x2 y2 1|
|x3 y3 1|
S=(1/2)*(x1y2*1+x2y3*1+x3y1*1-x1y3*1-x2y1*1-x3y2*1)
即用三角形的三个顶点坐标求其面积的公式为:
S=(1/2)*(x1y2+x2y3+x3y1-x1y3-x2y1-x3y2)