Problem How Many Triangles （HDU 5784）
题目大意
给定平面上的n个点（n《2000），询问可以组成多少个锐角三角形。
解题分析
直接统计锐角三角形较困难，考虑问题的反面，统计直角三角形、钝角三角形、平角三角形（暂时这么叫吧QAQ）。
首先枚举三角形的一个端点A，对其他点进行象限为第一关键字，极角为第二关键字排序。
然后使用三个指针，进行O（n）的扫描。
具体做法为用 i 指针指向三角形的第二个端点B。我们可以假想通过平移和旋转，把A点置于平面直角坐标系的原点，把B点置于x轴的正方向。那么可以与AB组成钝角或直角的点就在三四象限或者y轴。
将 j 指针指向第一象限内可以组成锐角的最靠后的点，将k指针从j + 1 开始扫描至最后一个可以组成钝角的点，然后统计对答案的贡献。
之后将 i 指针 +1，继续扫描。
注意一些特殊的情况，可以写个暴力对拍，造点小数据debug。
参考程序
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define eps 1e-8 struct P{
long long x,y;
int f;
friend P operator -(P a,P b){
return (P){a.x-b.x,a.y-b.y};
}
}a[],b[],S; int n,m; inline long long cross(P a,P b,P c){ //ab X ac
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
} inline int calc(P a){
if (a.x> && a.y==) return ;
if (a.x> && a.y>) return ;
if (a.x== && a.y>) return ;
if (a.x< && a.y>) return ;
if (a.x< && a.y==) return ;
if (a.x< && a.y<) return ;
if (a.x== && a.y<) return ;
if (a.x> && a.y<) return ;
} inline bool cmp(const P a,const P b) {
if (a.f<b.f) return true;
if (a.f>b.f) return false;
long long tmp=cross(S,a,b);
if (tmp>) return true;
return false;
} inline bool ok(P a,P b,P c){
long long tmp=(b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);
if (tmp>) return true;
return false;
} int main(){
while (~scanf("%d",&n)){
for (int i=;i<=n;i++) scanf("%I64d %I64d",&a[i].x,&a[i].y);
long long sum=;
for (int ii=;ii<=n;ii++){
S=a[ii]; m=;
for (int j=;j<=n;j++)
if (j!=ii) b[++m]=a[j];
for (int i=;i<=m;i++) b[i].f=calc(b[i]-S);
sort(b+,b+m+,cmp);
int i=,j=,k=;
while (ok(S,b[i],b[j]) && cross(S,b[i],b[j])>= && j<=m) j++;
if (j==m+) continue;
j--; k=j+;
while (i<=m)
{
if (!ok(S,b[i],b[k])){
while (!ok(S,b[i],b[k+]) && k<m) k++;
sum+=k-j;
}
i++;
if (j<i) j=i;
while (ok(S,b[i],b[j+]) && cross(S,b[i],b[j+])> && j<m) j++;
if (k<=j) k=j+;
if (k>m) break;
}
}
long long p=1ll*n*(n-)*(n-)/;
printf("%I64d\n",p-sum);
}
}