Submission #3015209
Source Code Expand
#include <bits/stdc++.h> using namespace std; struct BIT { long long n; vector<long long> dat; void initialize(long long n_input){ n = n_input + 1; dat.resize(n+1); for(int i = 0; i<=n; i++) dat[i] = 0; } long long sum(long long i){ long long s = 0; while(i >= 0){ s += dat[i]; i = (i & (i+1)) - 1; } return s; } void add(long long i, long long x){ while(i <= n){ dat[i] += x; i |= i+1; } } }; int inversion(const vector<int> arr){ BIT bit; bit.initialize(arr.size()); int ret = 0; for(int i=0; i<arr.size(); i++){ ret += i - bit.sum(arr[i]); bit.add(arr[i], 1); } return ret; } vector<vector<int>> abc; double mid; bool cmpx(int a, int b){ double aa = (double)(-abc[a][0]*mid+abc[a][2]) / abc[a][1]; double bb = (double)(-abc[b][0]*mid+abc[b][2]) / abc[b][1]; return aa < bb; } bool cmpy(int a, int b){ double aa = (double)(-abc[a][1]*mid+abc[a][2]) / abc[a][0]; double bb = (double)(-abc[b][1]*mid+abc[b][2]) / abc[b][0]; return aa < bb; } bool cmpdx(vector<int> a, vector<int> b){ double aa = (double)a[0] / a[1]; double bb = (double)b[0] / b[1]; return aa < bb; } bool cmpdy(vector<int> a, vector<int> b){ double aa = (double)a[1] / a[0]; double bb = (double)b[1] / b[0]; return aa < bb; } int main(){ long long i, j, k; int N; cin >> N; abc.resize(N); for(i=0; i<N; i++){ int a, b, c; cin >> a >> b >> c; abc[i] = {a, b, c}; } int half = (N*(N-1)/2+1)/2; vector<int> order(N); for(i=0; i<N; i++) order[i] = i; sort(abc.begin(), abc.end(), cmpdx); double ub = 1e9, lb = -1e9; for(i=0; i<70; i++){ mid = (ub+lb)/2; sort(order.begin(), order.end(),cmpx); int inv = inversion(order); if(inv<half){ lb = mid; }else{ ub = mid; } } double x = ub; sort(abc.begin(), abc.end(), cmpdy); ub = 1e9, lb = -1e9; for(i=0; i<70; i++){ mid = (ub+lb)/2; sort(order.begin(), order.end(),cmpy); int inv = inversion(order); if(inv<half){ lb = mid; }else{ ub = mid; } } double y = ub; cout << fixed << setprecision(10); cout << x << " " << y << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - CARtesian Coodinate |
User | betrue12 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 2570 Byte |
Status | AC |
Exec Time | 1699 ms |
Memory | 3236 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 800 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt, s3.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, s1.txt, s2.txt, s3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 1680 ms | 3108 KB |
02.txt | AC | 1674 ms | 3108 KB |
03.txt | AC | 1693 ms | 3108 KB |
04.txt | AC | 1654 ms | 3236 KB |
05.txt | AC | 1649 ms | 3108 KB |
06.txt | AC | 1693 ms | 3108 KB |
07.txt | AC | 1694 ms | 3236 KB |
08.txt | AC | 1678 ms | 3108 KB |
09.txt | AC | 1699 ms | 3108 KB |
10.txt | AC | 1649 ms | 3108 KB |
11.txt | AC | 1621 ms | 3108 KB |
12.txt | AC | 1627 ms | 3108 KB |
13.txt | AC | 1667 ms | 3108 KB |
14.txt | AC | 1622 ms | 3108 KB |
15.txt | AC | 1660 ms | 3108 KB |
16.txt | AC | 1672 ms | 3108 KB |
17.txt | AC | 1647 ms | 3108 KB |
18.txt | AC | 1648 ms | 3108 KB |
19.txt | AC | 1653 ms | 3108 KB |
20.txt | AC | 1662 ms | 3108 KB |
21.txt | AC | 1393 ms | 3108 KB |
22.txt | AC | 1408 ms | 3108 KB |
23.txt | AC | 1639 ms | 3108 KB |
24.txt | AC | 1685 ms | 3108 KB |
25.txt | AC | 1686 ms | 3108 KB |
26.txt | AC | 1695 ms | 3108 KB |
27.txt | AC | 1 ms | 256 KB |
28.txt | AC | 1 ms | 256 KB |
29.txt | AC | 1 ms | 256 KB |
30.txt | AC | 1 ms | 256 KB |
31.txt | AC | 1 ms | 256 KB |
32.txt | AC | 1 ms | 256 KB |
s1.txt | AC | 1 ms | 256 KB |
s2.txt | AC | 1 ms | 256 KB |
s3.txt | AC | 1 ms | 256 KB |