結果

問題 No.947 ABC包囲網
コンテスト
ユーザー 🍮かんプリン
提出日時 2020-06-19 00:54:09
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 3,609 bytes
コンパイル時間 1,519 ms
コンパイル使用メモリ 168,044 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-07-03 13:05:39
合計ジャッジ時間 6,281 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.06.19 00:54:05
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

struct vec {
private:
    ll _gcd(ll a, ll b) {
        return b ? _gcd(b, a % b) : a;
    }
public:
    ll x, y;
    int round;  
    vec() : x(0), y(0), round(0) {}
    vec(ll X, ll Y, int round = 0) : round(round) {
        int cx = (X >= 0) ? 1 : -1;
        int cy = (Y >= 0) ? 1 : -1;
        X = abs(X);
        Y = abs(Y);
        if (X == 0 && Y == 0) {
            x = 0, y = 0;
        } else {
            ll g = _gcd(X, Y);
            x = cx * X / g;
            y = cy * Y / g;
        }
    }
    vec operator+(const vec &v) const {
        return vec(x + v.x, y + v.y, round + v.round);
    }
    vec operator-(const vec &v) const {
        return vec(x - v.x, y - v.y, round - v.round);
    }
    
    vec operator-() const {
        return vec(-x, -y, -round);
    }
    
    vec rotate180() {
        if (*this >= vec(-1, 0, round)) {
            return vec(-x, -y, round + 1);
        }
        return vec(-x, -y, round);
    }
    
    vec rotate90() {
        if (*this >= vec(0, -1, round)) {
            return vec(-y, x, round + 1);
        }
        return vec(-y, x, round);
    }
    
    vec rotate_90() {
        if (*this < vec(0, 1, round)) {
            return vec(y, -x, round - 1);
        }
        return vec(y, -x, round);
    }
    
    bool operator<(const vec &v) const {
        if (round != v.round) return round < v.round;
        if (*this == v) return false;
        if (y > 0 && v.y > 0) {
            if ((x > 0 && v.x > 0) || (x < 0 && v.x < 0)) return y * v.x < x * v.y;
            if (x <= 0 && v.x >= 0) return false;
            return true;
        } else if (y < 0 && v.y < 0) {
            if ((x < 0 && v.x < 0) || (x > 0 && v.x > 0)) return y * v.x < x * v.y;
            if (x >= 0 && v.x <= 0) return false;
            return true;
        } else if (y > 0 && v.y < 0) {
            return true;
        } else if (y < 0 && v.y > 0) {
            return false;
        } else if (y == 0 && x > 0 && (v.y != 0 || (v.y == 0 && v.x < 0))) {
            return true;
        } else if (y == 0 && x < 0 && v.y < 0) {
            return true;
        } else if (v.y == 0 && v.x < 0 && y > 0) {
            return true;
        } else {
            return false;
        }
    }
    bool operator==(const vec &v) const {
        return x == v.x && y == v.y && round == v.round;
    }
    bool operator<=(const vec &v) const {
        return *this < v || *this == v;
    }
    bool operator>=(const vec &v) const {
        return !(*this < v);
    }
    bool operator>(const vec &v) const {
        return !(*this <= v);
    }
    friend std::ostream &operator<<(std::ostream &os, const vec &v) {
        return os << "[" << v.x << "," << v.y << "]";
    }
};
int main() {
    int n;
    cin >> n;
    vector< vec > v(n);
    for (int i = 0; i < n; i++) {
        int p, q;
        cin >> p >> q;
        v[i] = vec(p, q);
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++) {
        v.push_back(vec(v[i].x, v[i].y, 1));
    }
    v.push_back(vec(0,0,1000));
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int l = 0,r = 0;
        while(v[l] <= v[i].rotate180()) l++;
        for (int j = i + 1; j < n + i; j++) {
            if (v[i] == v[j]) continue;
            if (v[i].rotate180() <= v[j]) break;
            while(v[r] < v[j].rotate180()) {
                r++;
            }
            ans += r - l;
        }
    }
    cout << ans / 3 << endl;
    return 0;
}
0