蒟蒻求助计算几何!
查看原帖
蒟蒻求助计算几何!
138511
GreenDay楼主2020/5/28 09:13

求助qwq

调了2天了,不知道哪里错了,求大佬帮忙康康,蒟蒻感激不尽。

关于第三个点,它萎了。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
struct Point {
    ll x , y;
    Point(ll x = 0, ll y = 0) : x(x) , y(y) {}
    Point operator- (const Point &t) const {return Point(x-t.x , y-t.y);} 
    ll operator* (const Point &t) const {return x*t.y - y*t.x;}
};

int n , cnt;
Point point[2505] , vec[5005];

inline ll C(int n , int m) {
	ll res = 1;
	for(int j = 0 ; j < m ; ++j) res = res * (n - j) / (j + 1);
	return res;
}

int main() {
	cin >> n;
	for(int i = 1 ; i <= n ; ++i) cin >> point[i].x >> point[i].y;
	ll ans = 5 * C(n , 5);
	for(int i = 1 ; i <= n ; ++i) { 
		cnt = 0;
		for(int j = 1 ; j <= n ; ++j)
			if(j != i) vec[++cnt] = point[j] - point[i];
		sort(vec + 1 , vec + 1 + cnt , [&](Point a , Point b) {
			return a * b > 0;
		});
		memcpy(vec + 1 + cnt , vec + 1 , cnt * sizeof(Point));
		for(int l = 1 , r = 2 ; l <= cnt ; ++l) {
			while(vec[l] * vec[r] > 0) ++r;
			ans -= C(r - l - 1, 3);
		}
	}
	cout << ans << endl;
}
2020/5/28 09:13
加载中...