#407054 (C++14) No.947 ABC包囲網

• 問題: No.947 ABC包囲網
• ユーザー: zeke
• 提出日時: 2019-12-10 00:46:59
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,660 bytes
• コンパイル時間: 1,320 ms
• コンパイル使用メモリ: 105,136 KB
• 実行使用メモリ: 8,752 KB
• 最終ジャッジ日時: 2023-09-05 15:06:48
• 合計ジャッジ時間: 6,002 ms
• ジャッジサーバーID （参考情報）: judge12 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,376 KB
testcase_01	AC	2 ms; 4,376 KB
testcase_02	AC	2 ms; 4,376 KB
testcase_03	AC	2 ms; 4,376 KB
testcase_04	AC	2 ms; 4,380 KB
testcase_05	AC	2 ms; 4,376 KB
testcase_06	AC	2 ms; 4,380 KB
testcase_07	AC	2 ms; 4,376 KB
testcase_08	AC	2 ms; 4,376 KB
testcase_09	AC	2 ms; 4,376 KB
testcase_10	AC	2 ms; 4,376 KB
testcase_11	AC	2 ms; 4,376 KB
testcase_12	AC	1 ms; 4,376 KB
testcase_13	AC	1 ms; 4,380 KB
testcase_14	AC	2 ms; 4,380 KB
testcase_15	AC	15 ms; 4,944 KB
testcase_16	AC	4 ms; 4,396 KB
testcase_17	AC	6 ms; 4,388 KB
testcase_18	AC	19 ms; 4,728 KB
testcase_19	AC	19 ms; 4,516 KB
testcase_20	AC	19 ms; 4,464 KB
testcase_21	AC	19 ms; 4,652 KB
testcase_22	AC	20 ms; 4,820 KB
testcase_23	AC	19 ms; 4,380 KB
testcase_24	AC	19 ms; 4,380 KB
testcase_25	AC	19 ms; 4,776 KB
testcase_26	AC	19 ms; 4,612 KB
testcase_27	AC	18 ms; 4,824 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	--	-

ソースコード

/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
long long modMult(long long a, long long b, long long m)
{
    long long res = 0;
    long long exp = a % m;
    while (b)
    {
        if (b & 1)
        {
            res += exp;
            if (res > m)
                res -= m;
        }
        exp <<= 1;
        if (exp > m)
            exp -= m;
        b >>= 1;
    }
    return res;
}
long long powMod(long long a, long long b, long long m)
{
    long long res = 1;
    long long exp = a % m;
    while (b)
    {
        if (b & 1)
            res = modMult(res, exp, m);
        exp = modMult(exp, exp, m);
        b >>= 1;
    }
    return res;
}
//powMod(a,b,MOD)
//O(log(b))?
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
/*template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}*/
const double EPS = 1e-20;
double add(double l, double r)
{
    if (abs(l + r) < EPS * (abs(l) + abs(r)))
        return 0;
    return l + r;
}
//l-r は add(l,-r)
//l==r は add(l,-r)==0
struct Pt
{
    double x, y;
    Pt(double xx = 0, double yy = 0)
    {
        x = xx;
        y = yy;
    }
    Pt &operator=(const Pt &rhs)
    {
        x = rhs.x;
        y = rhs.y;
        return *this;
    }
    Pt &operator+=(const Pt &rhs)
    {
        x = add(x, rhs.x);
        y = add(y, rhs.y);
        return *this;
    }
    Pt &operator-=(const Pt &rhs)
    {
        x = add(x, -rhs.x);
        y = add(y, -rhs.y);
        return *this;
    }
    Pt &operator*=(const double &rhs)
    {
        x *= rhs;
        y *= rhs;
        return *this;
    }
    Pt &operator/=(const double &rhs)
    {
        x /= rhs;
        y /= rhs;
        return *this;
    }
};
Pt operator+(const Pt &a) { return a; }
Pt operator-(const Pt &a) { return Pt(-a.x, -a.y); }
Pt operator+(const Pt &lhs, const Pt &rhs)
{
    Pt ans = lhs;
    ans += rhs;
    return ans;
}
Pt operator-(const Pt &lhs, const Pt &rhs)
{
    Pt ans = lhs;
    ans -= rhs;
    return ans;
}
Pt operator*(const Pt &lhs, const double &rhs)
{
    Pt ans = lhs;
    ans *= rhs;
    return ans;
}
Pt operator*(const double &lhs, const Pt &rhs)
{
    Pt ans = rhs;
    ans *= lhs;
    return ans;
}
Pt operator/(const Pt &lhs, const double &rhs)
{
    Pt ans = lhs;
    ans /= rhs;
    return ans;
}
bool operator==(const Pt &lhs, const Pt &rhs)
{
    return add(lhs.x, -rhs.x) == 0 && add(lhs.y, -rhs.y) == 0;
}
bool operator!=(const Pt &lhs, const Pt &rhs) { return !(lhs == rhs); }
bool operator<(const Pt &lhs, const Pt &rhs)
{
    return add(lhs.x, -rhs.x) != 0 ? lhs.x < rhs.x : add(lhs.y, -rhs.y) < 0;
}
bool operator>(const Pt &lhs, const Pt &rhs) { return rhs < lhs; }
bool operator<=(const Pt &lhs, const Pt &rhs) { return !(lhs > rhs); }
bool operator>=(const Pt &lhs, const Pt &rhs) { return !(lhs < rhs); }
istream &operator>>(istream &is, Pt &rhs)
{
    double x, y;
    is >> x >> y;
    rhs = Pt(x, y);
    return is;
}
ostream &operator<<(ostream &os, const Pt &rhs)
{
    os << rhs.x << " " << rhs.y;
    return os;
}
double norm(const Pt &a) { return add(a.x * a.x, a.y * a.y); }
double abs(const Pt &a) { return sqrt(norm(a)); }
double dot(Pt a, Pt b) { return add(a.x * b.x, a.y * b.y); }
double cross(Pt a, Pt b) { return add(a.x * b.y, -a.y * b.x); }
int ccw(Pt a, Pt b, Pt c)
{
    b -= a;
    c -= a;
    if (cross(b, c) > 0)
        return +2; // counter clockwise
    if (cross(b, c) < 0)
        return -2; // clockwise
    if (dot(b, c) < 0)
        return +1; // c--a--b on line
    if (norm(c) < norm(b))
        return -1; // b--c--a on line
    return 0;      // a--b--c on line
}
//主に幾何問題に使うとよいです
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    vector<Pt> vec(n);
    Pt k = {0, 0};
    rep(i, n) cin >> vec[i];
    VV reg(n, V(n));
    rep(i,n){
        rep(j,n){
            reg[i][j] = ccw(k, vec[i], vec[j]);
          //  cout<<reg[i][j]<<" ";
        }
     //   cout<<endl;
    }
    
    VV reg2(n);
    VV reg3(n);
    rep(i,n){
        rep(j,n){
            if(reg[i][j]==2){
                reg2[i].push_back(j);
            }
            if (reg[i][j] == -2)
            {
                reg3[i].push_back(j);
            }
        }
    }
    ll res = 0;
    rep(i,n){
        rep(j,reg2[i].size()){
            rep(k,reg3[i].size()){
                if(reg[reg2[i][j]][reg3[i][k]]==2){
                    res++;
                }
            }
        }
    }
    cout << res/3 << endl;
}