HDU 3629(凸四角形の個数)
1954 ワード
タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=3629
标题:平面にn個の点をあげて、凸四角形はいくつありますか?
解析:各点について,凹四角形の個数は,C(n−1,3)−この点の同側の3点からなる三角形の個数に等しい.凸多角形の頂点の場合、
他の頂点は必ずこの頂点を通る直線の同側にある.
極角を計算するとき、負数(-pi~0)であれば2*piを加算し、0~2 piに角度を統一します.また、この問題に2つの点のクランプを順次統計します
角の場合、一回りした場合は角度を計算しにくいため、元の配列の後ろにn-1の点を順次加算し、角度が同じに2 pi加算
标题:平面にn個の点をあげて、凸四角形はいくつありますか?
解析:各点について,凹四角形の個数は,C(n−1,3)−この点の同側の3点からなる三角形の個数に等しい.凸多角形の頂点の場合、
他の頂点は必ずこの頂点を通る直線の同側にある.
極角を計算するとき、負数(-pi~0)であれば2*piを加算し、0~2 piに角度を統一します.また、この問題に2つの点のクランプを順次統計します
角の場合、一回りした場合は角度を計算しにくいため、元の配列の後ろにn-1の点を順次加算し、角度が同じに2 pi加算
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long LL;
const int N = 750;
const double PI = acos(-1.0);
struct Point
{
int x,y;
};
Point p[N];
double A[N];
int n;
double angle(double x,double y)
{
double t = y - x;
if(t < 0) t += 2*PI;
return t;
}
LL work()
{
LL t1 = (LL)n*(n-1)*(n-2)*(n-3)/24;
for(int k=0; k<n; k++)
{
int cnt = 0;
for(int i=0; i<n; i++)
{
if(k != i)
A[cnt++] = atan2((double)(p[i].y-p[k].y),(double)(p[i].x-p[k].x));
}
sort(A,A+n-1);
LL t2 = (LL)(n-1)*(n-2)*(n-3)/6;
for(int j=0,i=0; i<n-1; i++)
{
while(j<i+n-1)
{
if(angle(A[i],A[j%(n-1)])>PI) break;
j++;
}
t2 -= (LL)(j-i-1)*(j-i-2)/2;
}
t1 -= t2;
}
return t1;
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i=0; i<n; i++)
cin>>p[i].x>>p[i].y;
cout<<work()<<endl;
}
return 0;
}