[USACO 2010 Ope G]Triangle Counting

By way of example, consider 5 cows at these locations: -5,0 0,2 11,2 -11,-6 11,-5 Below is a schematic layout of the field from Betsy's point of view: ............|............ ............*..........*. ............|............ -------*----+------------ ............|............ ............|............ ............|............ ............|............ ............|..........*. .*..........|............ ............|............ All ten triangles below can be formed from the five points above: By inspection, 5 of them contain the origin and hence are 'golden'.

C++14(g++5.4) 解法, 执行用时: 45ms, 内存消耗: 3044K, 提交时间: 2019-09-29 18:40:18

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const ll N = 1e6+100, inf = 123456789;

ll t, n;

long long ans; 

struct led{
	ll x, y;
	double k;
} d[N];

bool cmp(led a, led b){
	return a.k < b.k;
}

int main(){
    
	scanf("%lld", &n);

	ans = (long long)(n * (n - 1) * (n - 2) / 6);

	for(ll i = 1; i <= n; i ++){
		scanf("%lld %lld", &d[i].x, &d[i].y);
		d[i].k = atan2(d[i].y, d[i].x);
	}
	
	sort(d + 1, d + n + 1, cmp);
	
	ll j = 2;
	
	for(ll i = 1; i <= n; i ++, t --){
		for( ; d[j].x * d[i].y - d[i].x * d[j].y < 0; j = j == n ? 1 : j + 1)
			t ++;
		ans -= (long long)(t * (t - 1) / 2);
	}
	
	printf("%lld", ans);
	
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 47ms, 内存消耗: 3028K, 提交时间: 2019-09-29 12:59:16

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
const int maxn=100100;
using namespace std;
long long ans, N;
struct point
{
    long long x, y;
    double th;
}pt[maxn];
bool operator<(point p1, point p2){return p1.th<p2.th;}
long long operator*(point p1, point p2){return p1.x*p2.y-p2.x*p1.y;}
int main()
{
	scanf("%lld",&N);
	for(int i=1;i<=N;i++) scanf("%lld%lld",&pt[i].x,&pt[i].y),pt[i].th=atan2(pt[i].y,pt[i].x);
	sort(pt+1,pt+N+1);
	ans=N*(N-1)*(N-2)/6;
	for(long long i=1,j=2,t=0;i<=N;i++,t--)
	{
		for(;pt[j]*pt[i]<0;j=j==N?1:j+1)t++;
		ans-=t*(t-1)/2;
	}
	printf("%lld",ans);
	return 0;
}

Python3(3.5.2) 解法, 执行用时: 602ms, 内存消耗: 25268K, 提交时间: 2019-09-30 23:21:05

from math import atan2
def func(coordinate):
    coordinate = sorted(coordinate,key=lambda t:atan2(t[0],t[1]))
    coordinate=coordinate
    r,t,sum=1,0,0
    for i in range(n):
        while r!=i and coordinate[i][0]*coordinate[r][1]<coordinate[i][1]*coordinate[r][0]:
            t+=1
            r=(r+1)%n
        sum+=int(t*(t-1)/2)
        if t>0:
            t-=1
    return sum


if __name__=="__main__":
    n = int(input())
    coordinate = []
    for i in range(n):
        s = list(map(int,input().split()))
        coordinate.append(s)
    print(int(n*(n-1)*(n-2)/6-func(coordinate)))

详情