Submission #1794467
Source Code Expand
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <cmath> #include <cstdio> #include <functional> #include <numeric> #include <stack> #include <queue> #include <map> #include <set> #include <utility> #include <sstream> #include <complex> #include <fstream> #include <bitset> #include <time.h> #include <tuple> using namespace std; typedef long long ll; typedef pair<ll, ll> P; typedef vector<ll> V; typedef complex<double> Point; #define PI acos(-1.0) #define EPS 1e-10 const ll INF = 1e12; const ll MOD = 1e9 + 7; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define rep(i,N) for(int i=0;i<(N);i++) #define ALL(s) (s).begin(),(s).end() #define EQ(a,b) (abs((a)-(b))<EPS) #define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) ) #define fi first #define se second #define N_SIZE (1LL << 20) #define NIL -1 #define MAX_N 100100 ll sq(ll num) { return num*num; } ll mod_pow(ll x, ll n) { if (n == 0)return 1; if (n == 1)return x%MOD; ll res = sq(mod_pow(x, n / 2)); res %= MOD; if (n % 2 == 1) { res *= x; res %= MOD; } return res; } ll mod_add(ll a, ll b) { return (a + b) % MOD; } ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; } ll mod_mul(ll a, ll b) { return a*b % MOD; } int n; Point p[2001]; int main() { cin >> n; rep(i, n) { double x, y; cin >> x >> y; p[i] = Point(x, y); } int r = 0, o = 0; rep(i, n) { //cout << "!" << i << endl; vector<double> vd; rep(j, n) { Point pp = p[j] - p[i]; if (i != j) { vd.push_back(atan2(pp.imag(), pp.real())); vd.push_back(atan2(pp.imag(), pp.real()) + 2.0 * PI); } } sort(ALL(vd)); //rep(j, vd.size())cout << vd[j] << endl; rep(j, vd.size() / 2) { auto it1 = upper_bound(ALL(vd), vd[j] + PI / 2.0 + EPS); auto it2 = lower_bound(ALL(vd), vd[j] + PI / 2.0 - EPS); auto ub = lower_bound(ALL(vd), vd[j] + PI - EPS); //cout << *it1 << " " << *it2 << " " << *ub << endl; r += (it1 - it2); o += (ub - it1); } //cout << "!!" << r << " " << o << endl; } ll num = n*(n - 1)*(n - 2) / 6; cout << num - o - r << " " << r << " " << o << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - 三角形の分類 |
User | jimmy |
Language | C++14 (GCC 5.4.1) |
Score | 30 |
Code Size | 2215 Byte |
Status | WA |
Exec Time | 1113 ms |
Memory | 384 KB |
Judge Result
Set Name | sample | subtask01 | subtask02 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 0 / 70 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt |
subtask01 | 01-00.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-handmade00.txt, 01-handmade01.txt, 01-handmade02.txt, 01-handmade03.txt, 01-handmade04.txt, 01-handmade05.txt, sample-01.txt, sample-02.txt |
subtask02 | 01-00.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-handmade00.txt, 01-handmade01.txt, 01-handmade02.txt, 01-handmade03.txt, 01-handmade04.txt, 01-handmade05.txt, 02-00.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-handmade00.txt, 02-handmade01.txt, 02-handmade02.txt, 02-handmade03.txt, 02-handmade04.txt, 02-handmade05.txt, sample-01.txt, sample-02.txt, sample-01.txt, sample-02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-00.txt | AC | 1 ms | 256 KB |
01-01.txt | AC | 1 ms | 256 KB |
01-02.txt | AC | 1 ms | 256 KB |
01-03.txt | AC | 1 ms | 256 KB |
01-04.txt | AC | 2 ms | 256 KB |
01-05.txt | AC | 2 ms | 256 KB |
01-06.txt | AC | 2 ms | 256 KB |
01-07.txt | AC | 4 ms | 256 KB |
01-08.txt | AC | 4 ms | 256 KB |
01-09.txt | AC | 4 ms | 256 KB |
01-10.txt | AC | 4 ms | 256 KB |
01-11.txt | AC | 4 ms | 256 KB |
01-12.txt | AC | 4 ms | 256 KB |
01-13.txt | AC | 4 ms | 256 KB |
01-14.txt | AC | 4 ms | 256 KB |
01-15.txt | AC | 4 ms | 256 KB |
01-16.txt | AC | 4 ms | 256 KB |
01-17.txt | AC | 4 ms | 256 KB |
01-18.txt | AC | 4 ms | 256 KB |
01-19.txt | AC | 4 ms | 256 KB |
01-handmade00.txt | AC | 2 ms | 256 KB |
01-handmade01.txt | AC | 4 ms | 256 KB |
01-handmade02.txt | AC | 2 ms | 256 KB |
01-handmade03.txt | AC | 4 ms | 256 KB |
01-handmade04.txt | AC | 4 ms | 256 KB |
01-handmade05.txt | AC | 4 ms | 256 KB |
02-00.txt | AC | 11 ms | 256 KB |
02-01.txt | AC | 42 ms | 256 KB |
02-02.txt | AC | 41 ms | 256 KB |
02-03.txt | AC | 128 ms | 256 KB |
02-04.txt | AC | 128 ms | 256 KB |
02-05.txt | AC | 128 ms | 256 KB |
02-06.txt | AC | 263 ms | 256 KB |
02-07.txt | AC | 263 ms | 256 KB |
02-08.txt | AC | 265 ms | 256 KB |
02-09.txt | AC | 264 ms | 256 KB |
02-10.txt | AC | 264 ms | 256 KB |
02-11.txt | AC | 270 ms | 384 KB |
02-12.txt | AC | 266 ms | 256 KB |
02-13.txt | WA | 1089 ms | 384 KB |
02-14.txt | WA | 1091 ms | 384 KB |
02-15.txt | WA | 1091 ms | 384 KB |
02-16.txt | WA | 1090 ms | 384 KB |
02-17.txt | WA | 1083 ms | 384 KB |
02-18.txt | WA | 1092 ms | 384 KB |
02-19.txt | WA | 1089 ms | 384 KB |
02-handmade00.txt | WA | 507 ms | 384 KB |
02-handmade01.txt | WA | 1087 ms | 384 KB |
02-handmade02.txt | WA | 601 ms | 384 KB |
02-handmade03.txt | WA | 1086 ms | 384 KB |
02-handmade04.txt | WA | 1113 ms | 384 KB |
02-handmade05.txt | WA | 1094 ms | 384 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |