[APIO2010 signaling]计算几何、性质->经典模型

【题目地址】http://www.apio.olympiad.org/
【算法分析】
取4个点，可以推出：
如果是构成凸四边形的话，有两种取法会覆盖完4个点。
如果是构成凹四边形的话，有1种取法会覆盖完4个点。
不要说正方形、矩形。。。题目说明不会有点在外接圆上的。
然后设取4个点中，构成凸四边形的有P个，凹四边形有Q个。
那么P+Q=C(n,4)
然后最终答案ans=(2*P+Q)/C(n,3)+3。
至于求Q。那么就是枚举那个凹四边形中的中心点，然后将其平移至原点，
问题转化成：求N个点中取三个点，过原点的三角形有多少个？
这个是一个经典问题。可以参考这里来解决：
http://hi.baidu.com/edwardmj/blog/item/40751a1454c50414962b4367.html
【CODE】
#include #include #include #include #define next(j) ((j)==n?1:j+1)
using namespace std;
typedef long long lld;
const int N=1505;
struct Point{int x,y;}a[N],tt[N];
int n;
int xx1,xx2;
lld F[N],ans,FM,P,Q;

void input(){
scanf("%d",&n);
int i;
for (i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
}

inline int get_xx(Point p){
if (p.x>=0 && p.y>0) return 1;
if (p.x>0 && p.y<=0) return 2;
if (p.x<=0 && p.y<0) return 3;
return 4;
}

inline int cj(Point &p0,Point &p1,Point &p2){
lld res=(lld)(p1.x-p0.x)*(lld)(p2.y-p0.y)-(lld)(p1.y-p0.y)*(lld)(p2.x-p0.x);
if (res<0) return -1;
if (res==0) return 0;
return 1;
}

inline bool cmp(Point x,Point y){
xx1=get_xx(x),xx2=get_xx(y);
if (xx1!=xx2) return xx1 return cj(a[0],x,y)<0;
}

void solve(){
sort(a+1,a+1+n,cmp);
ans+=(lld)(n)*(n-1)*(n-2)/6;
lld total;
int i,j=1;
for (i=1;i<=n;i++){
if (i==j) j=next(j);
while (i!=next(j) && cj(a[0],a[i],a[next(j)])<0) j=next(j);
if (j else total=j-i;
ans-=total*(total-1)/2;
}
}

inline void swap(Point &X,Point &Y){Point tmp=X; X=Y; Y=tmp;}

void work(){
FM=(lld)(n)*(n-1)*(n-2)/6;
ans=0;
memcpy(tt,a,sizeof(tt));
int i,j;
n;
for (i=1;i<=n;i++){
for (j=1;j<=n;j++) a[j]=tt[j];
swap(a[n],a[i]);
for (j=1;j a[j].x-=a[n].x;
a[j].y-=a[n].y;
}
n–;
solve();
n++;
}
Q=ans;
P=(lld)(n)*(n-1)*(n-2)*(n-3)/24-Q;
ans=2*P+Q;
printf("%.3lfn",(double)ans/(double)(FM)+3);
}

int main(){
freopen("signaling.in","r",stdin);
freopen("signaling.out","w",stdout);
input();
work();
}