[计算几何]JZOJ 3129 数三角形分析

Description

在一只大灰狼偷偷潜入Farmer Don的牛群被群牛发现后，贝西现在不得不履行着她站岗的职责。从她的守卫塔向下瞭望简直就是一件烦透了的事情。她决定做一些开发智力的小练习，防止她睡着了。

想象牧场是一个X，Y平面的网格。她将N只奶牛标记为1…N (1 <= N <= 100,000)，每只奶牛的坐标为X_i,Y_i (-100,000 <= X_i <= 100,000;-100,000 <= Y_i <= 100,000; 1 <= i <=N)。然后她脑海里想象着所有可能由奶牛构成的三角形。如果一个三角形完全包含了原点(0,0)，那么她称这个三角形为“黄金三角形”。原点不会落在任何一对奶牛的连线上。另外，不会有奶牛在原点。

给出奶牛的坐标，计算出有多少个“黄金三角形”。

Input

* 第一行：一个整数N

* 第2到第N+1行：每行两个整数X_i，Y_i，表示每只牛的坐标

Output

* 第一行: 一行包括一个整数，表示“黄金三角形的数量”

Sample Input

Sample Output

Data Constraint

Hint

考虑五只牛，坐标分别为(-5,0), (0,2), (11,2), (-11,-6), (11,-5)。

[计算几何]JZOJ 3129 数三角形
分析

我们先考虑把每个点向原点连一条直线，那么要构成一个经过原点的三角形都不可能在这条直线的同侧

那么我们把个点按极角排序，然后只统计直线的半边的非黄金三角形个数，就能不重复不遗漏了

答案等于总三角形个数减非黄金三角形个数

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct Point {
    ll x,y;
    double a;
    friend bool operator < (Point a,Point b) {
        return a.a<b.a;
    }
}a[N];
int n;
ll ans;

ll Multi(int i,int j) {
    return a[i].x*a[j].y-a[i].y*a[j].x;
}

void Calc() {
    int tot=0,now=1;
    for (int i=1;i<=n;i++) {
        while (now%n+1!=i&&Multi(i,now%n+1)>=1ll) now++,tot++;
        ans-=1ll*tot*(tot-1ll)/2ll;
        tot--;
    }
}

int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].a=atan2(a[i].y,a[i].x);
    sort(a+1,a+n+1);
    ans=1ll*n*(n-1ll)*(n-2ll)/6;
    Calc();
    printf("%lld",ans);
}

View Code

[计算几何]JZOJ 3129 数三角形 分析