BZOJ_1914
这个题目N好大，乱蒙的话大概也会想到先参考原点来个极角排序。
接着考虑怎么去计算了，一开始想直接算满足要求的三角形，不过想了几种思路之后还是没法解决。后来突然想到不妨尝试一下计算不满足要求的三角形，这时会发现原点和三个点的连线的跨度小于180度，也就是说两条夹角小于180度的射线中间又夹了一条射线，这样的三角形才会是不符合要求的。这样我们枚举不符合要求的三角形上按极角序出现的第一个点，这时如果我们按极角序找到两射线夹角小于180度的最远的那个点，就可以O(1)计算了。
#include#include #include #define MAXD 200010typedef long long LL;int N;struct Point{ int x, y, a; Point(){} Point(int _x, int _y, int _a) : x(_x), y(_y), a(_a){} bool operator < (const Point &t) const { if(a == t.a) return (LL)y * t.x < (LL)x * t.y; return a < t.a; }}p[MAXD];LL det(int x1, int y1, int x2, int y2){ return (LL)x1 * y2 - (LL)x2 * y1;}void init(){ for(int i = 0; i < N; i ++) { int x, y, area; scanf("%d%d", &x, &y); if(x >= 0 && y >= 0) area = 2; else if(x <= 0 && y <= 0) area = 0; else if(x > 0 && y < 0) area = 1; else area = 3; p[i] = Point(x, y, area); } std::sort(p, p + N); for(int i = 0; i < N; i ++) p[i + N] = p[i];}void solve(){ LL ans = 0; int j = 0; for(int i = 0; i < N; i ++) { while(j < i + N && det(p[i].x, p[i].y, p[j].x, p[j].y) >= 0) ++ j; if(j - i >= 3) ans += (LL)(j - i - 2) * (j - i - 1) / 2; } printf("%lld\n", (LL)N * (N - 1) * (N - 2) / 6 - ans);}int main(){ while(scanf("%d", &N) == 1) { init(); if(N < 3) printf("0\n"); else solve(); } return 0;}