結果

問題 No.947 ABC包囲網
ユーザー 🍮かんプリン🍮かんプリン
提出日時 2020-06-19 00:55:52
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 3,618 bytes
コンパイル時間 1,609 ms
コンパイル使用メモリ 157,160 KB
実行使用メモリ 8,004 KB
最終ジャッジ日時 2023-09-16 12:32:45
合計ジャッジ時間 6,069 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 12 ms
4,376 KB
testcase_16 AC 5 ms
4,380 KB
testcase_17 AC 8 ms
4,380 KB
testcase_18 AC 48 ms
4,376 KB
testcase_19 AC 47 ms
4,376 KB
testcase_20 AC 48 ms
4,376 KB
testcase_21 AC 48 ms
4,376 KB
testcase_22 AC 48 ms
4,380 KB
testcase_23 AC 14 ms
4,380 KB
testcase_24 AC 14 ms
4,376 KB
testcase_25 AC 14 ms
4,376 KB
testcase_26 AC 14 ms
4,376 KB
testcase_27 AC 14 ms
4,376 KB
testcase_28 TLE -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
testcase_57 -- -
testcase_58 -- -
testcase_59 -- -
権限があれば一括ダウンロードができます

ソースコード

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;
    int l = 0;
    for (int i = 0; i < n; i++) {
        int 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