HDU - 5784 https://vjudge.net/problem/445574/origin
感觉好久没写这种题了啊.. 感觉细节好多.
对每个点极角排序统计钝角和直角, 还有三点共线的.
- #pragma GCC optimize(2)
- #pragma GCC optimize(3)
- #include<bits/stdc++.h>
- #define LL long long
- #define LD long double
- #define ull unsigned long long
- #define fi first
- #define se second
- #define mk make_pair
- #define PLL pair<LL, LL>
- #define PLI pair<LL, int>
- #define PII pair<int, int>
- #define SZ(x) ((int)x.size())
- #define ALL(x) (x).begin(), (x).end()
- #define fio iOS::sync_with_stdio(false); cin.tie(0) ;
- using namespace std;
- const int N = 4000 + 7;
- const int inf = 0x3f3f3f3f;
- const LL INF = 0x3f3f3f3f3f3f3f3f;
- const int mod = (int)1e9 + 7;
- const double eps = 1e-8;
- const double PI = acos(-1);
- template<class T, class S> inline void add(T &a, S b) {a += b; if(a>= mod) a -= mod;}
- template<class T, class S> inline void sub(T &a, S b) {a -= b; if(a <0) a += mod;}
- template<class T, class S> inline bool chkmax(T &a, S b) {return a <b ? a = b, true : false;}
- template<class T, class S> inline bool chkmin(T &a, S b) {return a> b ? a = b, true : false;}
- //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- struct Point {
- LL x, y;
- Point(LL x = 0, LL y = 0) : x(x), y(y) {}
- Point operator + (const Point &rhs) const {
- return Point(x + rhs.x, y + rhs.y);
- }
- Point operator - (const Point &rhs) const {
- return Point(x - rhs.x, y - rhs.y);
- }
- int quan() {
- return y <0 || y == 0 && x <0;
- }
- };
- LL Det(const Point &A, const Point &B) {
- return A.x * B.y - B.x * A.y;
- }
- LL Dot(const Point &A, const Point &B) {
- return A.x * B.x + A.y * B.y;
- }
- bool operator <(Point A, Point B) {
- if(A.quan() != B.quan()) return A.quan() <B.quan();
- else return Det(A, B)> 0;
- }
- bool equ(Point A, Point B) {
- if(A <B) return false;
- if(B <A) return false;
- return true;
- }
- LL c2(int x) {
- return 1LL * x * (x - 1) / 2;
- }
- int n;
- Point a[N], b[N];
- bool check(Point A, Point B) {
- if(Det(A, B) == 0) return false;
- if(Dot(A, B) <= 0) return false;
- return true;
- }
- int main() {
- while(scanf("%d", &n) != EOF) {
- for(int i = 1; i <= n; i++) {
- scanf("%lld%lld", &a[i].x, &a[i].y);
- }
- LL ans = 0, tmp = 0;
- for(int o = 1; o <= n; o++) {
- int tot = 0;
- for(int j = 1; j <= n; j++) {
- if(j == o) continue;
- b[tot++] = a[j] - a[o];
- }
- sort(b, b + tot);
- for(int i = 0; i <tot; i++) {
- b[i + tot] = b[i];
- }
- int pt1 = 0, pt2 = 0;
- for(int i = 0, j = 0; i <tot; i = j) {
- while(j <i + tot && equ(b[i], b[j])) j++;
- chkmax(pt1, j);
- while(pt1 <i + tot && Dot(b[i], b[pt1])> 0 && Det(b[i], b[pt1])> 0) pt1++;
- chkmax(pt2, pt1);
- while(pt2 <i + tot && Det(b[i], b[pt2])> 0) pt2++;
- ans += 1LL * (pt2 - pt1) * (j - i);
- }
- for(int i = 0, j = 0; i < tot; i = j) {
- j = i;
- while(j < i + tot && equ(b[i], b[j])) j++;
- tmp += c2(j - i);
- }
- }
- ans = 1LL * n * (n - 1) * (n - 2) / 6 - ans - tmp / 2;
- printf("%lld\n", ans);
- }
- return 0;
- }
- /*
- */
来源: http://www.bubuko.com/infodetail-3187786.html