Submission #1112648
Source Code Expand
#include <algorithm> #include <cassert> #include <cfloat> #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <deque> #include <iomanip> #include <iostream> #include <limits> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <vector> #define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i)) #define rep(i,n) FOR(i,0,n) #define pb push_back #define all(v) begin(v), end(v) #define debug(x) cerr<< #x <<": "<<x<<endl #define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<vector<int> > vvi; typedef vector<ll> vll; typedef vector<vector<ll> > vvll; template<class T> using vv=vector<vector< T > >; typedef pair<double, int> pdi; #define EPS 1e-14 int main() { int n; scanf("%d", &n); vi x(n), y(n); rep (i, n) { scanf("%d %d", &x[i], &y[i]); } ll ei, cho, don, devnull; ei = cho = don = devnull = 0; rep (i, n) { vector<double> theta; theta.reserve(n); rep (j, n) { if (i == j) { continue; } int dx = x[j] - x[i]; int dy = y[j] - y[i]; double tj = atan2(dy, dx); theta.push_back(tj); } sort(all(theta)); vector<double> ar; ar.reserve(3 * n); rep (j, n-1) { ar.push_back(theta[j] - 2*M_PI); } rep (j, n-1) { ar.push_back(theta[j]); } rep (j, n-1) { ar.push_back(theta[j] + 2*M_PI); } assert(is_sorted(all(ar))); int sz = (int)ar.size(); vvi tpa(n-1, vi(10, 0)); rep (k, 5) { tpa[0][2*k] = lower_bound(all(ar), theta[0] + (k-2) * M_PI/2 - EPS) - begin(ar); tpa[0][2*k+1] = upper_bound(all(ar), theta[0] + (k-2) * M_PI/2 + EPS) - begin(ar); } FOR (j, 1, n-1) { tpa[j][0] = tpa[j-1][0]; while (ar[tpa[j][0]] < theta[j] + (-2) * M_PI/2 - EPS && tpa[j][0] < sz-1) { tpa[j][0] += 1; } tpa[j][1] = max(tpa[j-1][1], tpa[j][0]); while (ar[tpa[j][1]] <= theta[j] + (-2) * M_PI/2 + EPS && tpa[j][1] < sz-1) { tpa[j][1] += 1; } FOR (k, 1, 5) { tpa[j][2*k] = max(tpa[j-1][2*k], tpa[j][2*k-1]); while (ar[tpa[j][2*k]] < theta[j] + (k-2) * M_PI/2 - EPS && tpa[j][2*k] < sz-1) { tpa[j][2*k] += 1; } tpa[j][2*k+1] = max(tpa[j-1][2*k+1], tpa[j][2*k]); while (ar[tpa[j][2*k+1]] <= theta[j] + (k-2) * M_PI/2 + EPS && tpa[j][2*k+1] < sz-1) { tpa[j][2*k+1] += 1; } } } rep (j, n-1) { don += tpa[j][2] - tpa[j][1]; cho += tpa[j][3] - tpa[j][2]; devnull += tpa[j][5] - tpa[j][4] - 1; cho += tpa[j][7] - tpa[j][6]; don += tpa[j][8] - tpa[j][7]; } } cho /= 2; don /= 2; devnull /= 2; ei = (ll)n * (n-1) * (n-2) / 6 - cho - don - devnull; printf("%lld %lld %lld\n", ei, cho, don); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 三角形の分類 |
User | tspcx |
Language | C++14 (Clang 3.8.0) |
Score | 100 |
Code Size | 3103 Byte |
Status | AC |
Exec Time | 888 ms |
Memory | 888 KB |
Judge Result
Set Name | sample | subtask01 | subtask02 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 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 | 8 ms | 888 KB |
01-01.txt | AC | 2 ms | 256 KB |
01-02.txt | AC | 1 ms | 256 KB |
01-03.txt | AC | 1 ms | 256 KB |
01-04.txt | AC | 1 ms | 256 KB |
01-05.txt | AC | 2 ms | 256 KB |
01-06.txt | AC | 2 ms | 256 KB |
01-07.txt | AC | 3 ms | 256 KB |
01-08.txt | AC | 3 ms | 256 KB |
01-09.txt | AC | 3 ms | 256 KB |
01-10.txt | AC | 3 ms | 256 KB |
01-11.txt | AC | 3 ms | 256 KB |
01-12.txt | AC | 3 ms | 256 KB |
01-13.txt | AC | 3 ms | 256 KB |
01-14.txt | AC | 3 ms | 256 KB |
01-15.txt | AC | 3 ms | 256 KB |
01-16.txt | AC | 4 ms | 256 KB |
01-17.txt | AC | 3 ms | 256 KB |
01-18.txt | AC | 3 ms | 256 KB |
01-19.txt | AC | 3 ms | 256 KB |
01-handmade00.txt | AC | 2 ms | 256 KB |
01-handmade01.txt | AC | 3 ms | 256 KB |
01-handmade02.txt | AC | 2 ms | 256 KB |
01-handmade03.txt | AC | 3 ms | 256 KB |
01-handmade04.txt | AC | 3 ms | 256 KB |
01-handmade05.txt | AC | 3 ms | 256 KB |
02-00.txt | AC | 10 ms | 256 KB |
02-01.txt | AC | 36 ms | 256 KB |
02-02.txt | AC | 36 ms | 256 KB |
02-03.txt | AC | 107 ms | 384 KB |
02-04.txt | AC | 107 ms | 384 KB |
02-05.txt | AC | 108 ms | 384 KB |
02-06.txt | AC | 219 ms | 384 KB |
02-07.txt | AC | 219 ms | 384 KB |
02-08.txt | AC | 219 ms | 384 KB |
02-09.txt | AC | 219 ms | 384 KB |
02-10.txt | AC | 220 ms | 384 KB |
02-11.txt | AC | 219 ms | 384 KB |
02-12.txt | AC | 219 ms | 384 KB |
02-13.txt | AC | 887 ms | 512 KB |
02-14.txt | AC | 887 ms | 512 KB |
02-15.txt | AC | 886 ms | 512 KB |
02-16.txt | AC | 886 ms | 512 KB |
02-17.txt | AC | 884 ms | 512 KB |
02-18.txt | AC | 885 ms | 512 KB |
02-19.txt | AC | 885 ms | 512 KB |
02-handmade00.txt | AC | 418 ms | 384 KB |
02-handmade01.txt | AC | 888 ms | 512 KB |
02-handmade02.txt | AC | 495 ms | 384 KB |
02-handmade03.txt | AC | 884 ms | 512 KB |
02-handmade04.txt | AC | 885 ms | 512 KB |
02-handmade05.txt | AC | 888 ms | 512 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |