【BZOJ1914】数三角形（组合数，极角排序）

题面

BZOJ权限题

良心洛谷

题解

这种姿势很吼啊，表示计算几何啥的一窍不通来着。

题目就是这样，正难则反，所以我们不考虑过原点的三角形，

反过来，总数减去不包含原点的三角形。

这个怎么计算呢？

我们每次先确定一个点，那么，所有在这个点和原点的连线下方的点都是可行的，

那么极角排序之后发现这就是一段连续的区间，

所以直接线性扫一遍就好了，组合数算算就没问题了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

#define MAX 100100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=true,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return t?-x:x;

}

struct Node{int x,y;double d;}a[MAX];

bool operator<(Node a,Node b){return a.d<b.d;}

bool Slope(Node a,Node b){return 1ll*a.x*b.y-1ll*a.y*b.x>=0;}

int n;ll ans;

int main()

{

	n=read();ans=1ll*n*(n-1)*(n-2)/6;

	for(int i=0;i<n;++i)a[i].x=read(),a[i].y=read(),a[i].d=atan2(a[i].y,a[i].x);

	sort(&a[0],&a[n]);

	for(int i=0,r=0,t=0;i<n;++i)

	{

		while((r+1)%n!=i&&Slope(a[i],a[(r+1)%n]))++t,++r;

		ans-=1ll*t*(t-1)/2;--t;

	}

	printf("%lld\n",ans);

	return 0;

}