HDU 5784 数锐角三角形个数（极角排列+尺取法）
http://acm.hdu.edu.cn/showproblem.php?pid=5784
How Many Triangles
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1773 Accepted Submission(s): 591
Problem Description
Alice has n points in two-dimensional plane. She wants to know how many different acute triangles they can form. Two triangles are considered different if they differ in at least one point.
Input
The input contains multiple test cases.
For each test case, begin with an integer n,
next n lines each contains two integers xi and yi.
3≤n≤2000
0≤xi,yi≤1e9
Any two points will not coincide.
For each test case, begin with an integer n,
next n lines each contains two integers xi and yi.
3≤n≤2000
0≤xi,yi≤1e9
Any two points will not coincide.
Output
For each test case output a line contains an integer.
Sample Input
3
1 1
2 2
2 3
3
1 1
2 3
3 2
4
1 1
3 1
4 1
2 3
Sample Output
0 1 2
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#pragma warning(disable:4996)
struct Point
{
int x, y;
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
Point operator+(const Point &a)const
{
return Point(x + a.x, y + a.y);
}
Point operator-(const Point &a)const
{
return Point(x - a.x, y - a.y);
}
Point operator=(const Point &a)
{
x = a.x; y = a.y;
return *this;
}
}py[5005];
ll det(const Point &a, const Point &b)
{
return (ll)a.x*b.y - (ll)a.y*b.x;
}
ll dot(const Point &a, const Point &b)
{
return a.x * 1ll * b.x + a.y * 1ll * b.y;
}
bool p_cmp(const Point &a, const Point &b)
{
if ((ll)a.y*b.y <= 0)
{
if (a.y > 0 || b.y > 0) return a.y < b.y;
if (a.y == 0 && b.y == 0) return a.x < b.x;
}
return det(a, b) > 0;
}
int n;
ll dun = 0;
ll rui = 0;
void solve(int now)
{
Point pd[10005];
int nn = n - 1;
int num = 0;
for (int i = 1; i <= n; i++)
{
if (i != now)pd[++num] = py[i] - py[now];
}
sort(pd + 1, pd + num + 1, p_cmp);
/*for (int i = 1; i < n; i++)
{
cout << pd[i].x << " " << pd[i].y << endl;
}*/
for (int i = 1; i <= n - 1; i++)
pd[i + n - 1] = pd[i];
//cout<<"sort ok"<<endl;
int j = 1, k = 1, l = 1, p = 1;//相同极角的点的位置，锐角极角的位置，直角极角的位置,钝角极角的位置
for (int i = 1; i <= n - 1; i++)
{
while (j < i + nn && det(pd[i], pd[j]) == 0 && dot(pd[i], pd[j])>0)
j++;//平行的
k = max(j, k);
//cout << "j " << j << endl;
while (k < i + nn && det(pd[i], pd[k])>0 && dot(pd[i], pd[k]) > 0)
k++;//锐角
//cout << "k " << k << endl;
l = max(k, l);
while (l < i + nn && det(pd[i], pd[l])>0 && dot(pd[i], pd[k]) == 0)
l++;//直角
//cout << "l " << l << endl;
p = max(l, p);
while (p < i + nn && det(pd[i], pd[p])>0)
p++;//钝角
//cout << "p " << p << endl;
rui += k - j;//锐角个数
dun += p - l + l - k;//p-l是钝角的个数，l-k是直角的个数
}
}
int main()
{
while (scanf("%d", &n) != EOF)
{
rui = 0; dun = 0;
for (int i = 1; i <= n; i++)
{
cin >> py[i].x >> py[i].y;
}
if (n == 1 || n == 2)
{
cout << 0; return 0;
}
for (int i = 1; i <= n; i++)
{
solve(i);
}
ll ans;
ans = (rui - dun * 2) / 3;
printf("%I64d\n", ans);
}
}
