結果

問題 No.1144 Triangles
ユーザー catuppercatupper
提出日時 2020-08-01 00:42:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 616 ms / 3,000 ms
コード長 4,146 bytes
コンパイル時間 1,055 ms
コンパイル使用メモリ 99,184 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-06 23:01:52
合計ジャッジ時間 9,543 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 616 ms
5,376 KB
testcase_05 AC 603 ms
5,376 KB
testcase_06 AC 615 ms
5,376 KB
testcase_07 AC 616 ms
5,376 KB
testcase_08 AC 606 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 555 ms
5,376 KB
testcase_15 AC 552 ms
5,376 KB
testcase_16 AC 585 ms
5,376 KB
testcase_17 AC 591 ms
5,376 KB
testcase_18 AC 599 ms
5,376 KB
testcase_19 AC 82 ms
5,376 KB
testcase_20 AC 5 ms
5,376 KB
testcase_21 AC 6 ms
5,376 KB
testcase_22 AC 573 ms
5,376 KB
testcase_23 AC 34 ms
5,376 KB
testcase_24 AC 565 ms
5,376 KB
testcase_25 AC 181 ms
5,376 KB
testcase_26 AC 19 ms
5,376 KB
testcase_27 AC 14 ms
5,376 KB
testcase_28 AC 113 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<complex>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef Int Real;
typedef complex<Real> CP;

class Vec{
public:
    Real x, y;
    Vec(Real x = 0, Real y = 0):x(x),y(y){}

    Vec &read(){
        cin >> x >> y;
        return *this;
    }

    void print(){
        printf("%.10lf %.10lf\n", double(x), double(y));
    }

    bool operator<(const Vec &other) const{
        if(x < other.x)return true;
        if(x == other.x && y < other.y)return true;
        return false;
    }
    
    Vec operator+(const Vec &other)
        {
            Vec result = *this;
            result.x += other.x;
            result.y += other.y;
            return result;
        }

    Vec operator-(const Vec &other)
        {
            Vec result = *this;
            result.x -= other.x;
            result.y -= other.y;
            return result;
        }

    Vec operator*(const Real &k)
        {
            Vec result = *this;
            result.x *= k;
            result.y *= k;
            return result;
        }

    Vec operator/(const Real &k)
        {
            Vec result = *this;
            result.x /= k;
            result.y /= k;
            return result;
        } 
    
    Real cross(const Vec &other)
        {
            return x*other.y - y*other.x;
        }

    Real dot(const Vec &other){
        return x*other.x + y*other.y;
    }
    bool operator==(const Vec &other) const
        {
            return abs(x - other.x) < EPS && abs(y - other.y) < EPS;
        }
    bool operator!=(const Vec &other) const
        {
            return !(*this == other);
        }

    double norm()
        {
            return sqrt(x*x+y*y);
        }

    Real norm2()
        {
            return x*x+y*y;
        }

    Vec standard(){
        Vec result = *this;
        return result/result.norm();
    }
};

//cw:1, ccw:-1, other:0
Int CCW(Vec a, Vec b, Vec c){
    b = b - a;
    c = c - a;
    if(b.cross(c) > EPS)return -1;
    if(b.cross(c) < -EPS)return 1;
    return 0;
}

Real dist(Vec a, Vec b){
    return (a-b).norm();
}


//sort by atan2
//y=0, x < 0 is base
//atan2(0,0) == 0
bool arg_comp(Vec a, Vec b){
    int up_down_a = a.y > 0 || (a.y == 0 && a.x >= 0);
    int up_down_b = b.y > 0 || (b.y == 0 && b.x >= 0);
    if(up_down_a != up_down_b)return up_down_a < up_down_b;   
    if(a.x * b.y == a.y * b.x)return a.norm2() < b.norm2();
    return CCW(Vec(0,0), a, b) == -1;
}


Int solve(vector<Vec> &given_points){
    vector<Vec> points;
    Int ans = 0;
    for(auto &p:given_points)if(p != Vec(0,0))points.push_back(p);
    int n = points.size();
    sort(points.begin(), points.end(), arg_comp);
    Vec plus, minus;
    for(auto p:points){
        minus = minus + p;
    }
    
    for(int i = 0, r = 0;i < n;i++){
        if(i == r){
            while(points[i] == points[r]){                
                minus = minus - points[r];
                plus = plus + points[r];
                (r+=1)%=n;
                if(i == r)break;
            }
        }
        while(points[i] != points[r] && CCW(Vec(0,0), points[i], points[r]) != 1){
            minus = minus - points[r];
            plus = plus + points[r];
            (r+=1)%=n;            
        }
        (ans += points[i].cross(plus - minus)) %= MOD;
        plus = plus - points[i];
        minus = minus + points[i];
    }
    return ans;
}



int main(){
    Int n, ans = 0;
    cin >> n;
    vector<Vec> points(n);
    for(auto &p:points)p.read();

    for(int i = 0;i < n;i++){
        Vec origin = points[i];
        for(auto &p:points)p = p - origin;
        (ans += solve(points)) %= MOD;
        for(auto &p:points)p = p + origin;
    }
    while(ans % 6)ans += MOD;
    ans /= 6;ans %= MOD;
    if(ans < 0)ans += MOD;
    cout << ans << endl;
    return 0;
}
0