[坑][计算几何][极角排序][利用已有信息] UVALive 4064 Magnetic Train Tracks

https://cn.vjudge.net/problem/UVALive-4064

简单的极角排序应用，枚举每个点作为角点，然后按照角度顺时针枚举另一个点，在这个过程中递推记录下对于枚举的点有多少个钝角/直角出现。由于一个钝角/直角唯一的对应一个钝角/直角三角形，因此最后只需要把C(n,3)-钝角数量作为答案即可。

坑点：lrj的书上和各位dalao的blog都说的是锐角或直角，呵呵，wa了两个多小时最后翻别人代码发现是只能锐角不能直角，服了，改了就过了，也不知道网上这么多人都写得锐角或者直角是怎么写出来只能锐角的代码的。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

struct Point
{
    int x, y;
} ps[1205], tps[1205];

LL ans;
int n,id[2405];;
double ang[1205];
inline int prod(Point a, Point b) { return a.x * b.x + a.y * b.y; }
inline int cross(Point a, Point b) { return a.x * b.y - b.x * a.y; }
bool cmp(int a, int b) { return ang[a] > ang[b]; }

void calc(int s)
{
    int cx = ps[s].x, cy = ps[s].y;
    LL res = 0;
    for (int i = 1, t = 1; i <= n; i++)
        if (i != s)
        {
            tps[i].x = ps[i].x - cx, tps[i].y = ps[i].y - cy;
            ang[i] = atan2(tps[i].y, tps[i].x);
            id[t++] = i;
        }
    sort(id + 1, id + n, cmp);
    for (int i = 1; i < n; i++)
        id[n - 1 + i] = id[i];
    int o1 = 2, o2 = 2, o3 = n; //o3 is the current rightmost point
    for (int i = 1; i < n; i++)
    {
        o3 = n - 1 + i;
        while (o1 < o3 && cross(tps[id[o3]], tps[id[o1]]) <= 0)o1++; //over the 180 degree
        if (o1 == o3)continue;
        o2 = max(o1, o2);
        while (o2 < o3 && prod(tps[id[o3]], tps[id[o2]]) <= 0)o2++;
        if (prod(tps[id[o3]], tps[id[o1]]) > 0)continue;
        res += o2 - o1;
    }
    ans += res;
    return;
}

int main()
{
    int cs = 0;
    while (~scanf("%d", &n) && n)
    {
        cs++;
        ans = 0;
        printf("Scenario %d:\n", cs);
        for (int i = 1; i <= n; i++)
            scanf("%d%d", &ps[i].x, &ps[i].y);
        if (n < 3){printf("There are 0 sites for making valid tracks\n");continue;}
        for (int i = 1; i <= n; i++)
            calc(i);
        printf("There are %d sites for making valid tracks\n",(1LL * n * (n - 1) * (n - 2) / 6) - ans);
    }
    return 0;
}