题目概述

有 $n$ 个点，选出 $6$ 个点使得能够组成两个不相交的三角形，求方案数。

解题报告

几何神题，可以证明两个不相交的三角形之间恰好有两条切线（画了几个好像没什么毛病，反正我不会证明），所以我们可以枚举两个点来枚举切线，然后计算顺时针方向和逆时针方向点的个数，组合一下就行了。

计算顺时针方向和逆时针方向的点的个数只需要按照极角排序，然后每次维护一下分界点。

示例程序

第一次用极角排序……感觉写的很丑……算逆时针方向个数其实不需要预处理 $dis_{i,j}$ ，分类讨论下就可以了……

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;typedef long double DB;
const int maxn=2000;const DB pi=acos(-1);

int n,m,dis[maxn+5][maxn+5];struct Point {int x,y;DB ang;}a[maxn+5],p[maxn+5];LL ans;

inline bool operator < (const Point &a,const Point &b) {return a.ang<b.ang;}
inline Point operator - (const Point &a,const Point &b) {return (Point){a.x-b.x,a.y-b.y};}
inline LL Cross(const Point &a,const Point &b) {return (LL)a.x*b.y-(LL)a.y*b.x;}
#define Suf(x) ((x)<m?(x)+1:1)
inline LL Count(int A,int B) {int L=dis[A][B],R=n-2-L;return (LL)L*(L-1)/2*R*(R-1)/2;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    m=n-1;for (int i=1;i<=m;i++) for (int j=i;Suf(j)!=i;j=Suf(j)) dis[i][Suf(j)]=dis[i][j]+1;
    for (int i=(m=0,1);i<=n;i++,m=0){
        for (int j=1;j<=n;j++)
            if (i^j) {p[++m]=a[j];p[m].ang=atan2(a[j].y-a[i].y,a[j].x-a[i].x);if (p[m].ang<0) p[m].ang+=pi*2;}
        sort(p+1,p+1+m);int pos=1;for (int j=2;j<=m;j++) if (Cross(p[1]-a[i],p[j]-a[i])>0) pos=j;ans+=Count(1,pos);
        for (int j=2;j<=m;j++) {while (Cross(p[j]-a[i],p[Suf(pos)]-a[i])>0) pos=Suf(pos);ans+=Count(j,pos);}
    }return printf("%lld\n",ans>>1),0;
}