Submission #2118312
Source Code Expand
#include<iostream> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<queue> using namespace std; typedef long long ll; typedef pair<int,int> P; #define pb push_back #define fr first #define sc second const long double EPS = 0.00000000001; struct BIT{ int siz; int a[(1<<16)+10]; void init(int siz_ = 1<<16){ siz = siz_; for(int i = 1 ; i <= siz ; i ++){ a[i] = 0; } } void add(int k,int x = 1){ while(k <= siz){ a[k] += x; k += k&-k; } } int sum(int k){ int ret = 0; while(k > 0){ ret += a[k]; k -= k&-k; } return ret; } }bit; int N; long double A[40002]; long double B[40002]; long double C[40002]; int inv(vector<pair<long double,long double>> *vec){ /*for(int i = 0 ; i < vec->size() ; i ++){ cout << (*vec)[i].fr << " " << (*vec)[i].sc << endl; }*/ vector<pair<long double,int>> a; for(int i = 0 ; i < vec->size() ; i ++){ a.pb(pair<long double,int>((*vec)[i].sc,i+1)); } sort(a.begin(),a.end()); int ret = 0; bit.init(); for(int i = 0 ; i < a.size() ; i ++){ ret += bit.sum(a[i].sc); bit.add(a[i].sc); } return N*(N-1)/2-ret; } long double sol(){ long double l = -200000000.0 , r = 200000000.0; while(l+EPS < r){ long double m = (l+r)/2.0; vector<pair<long double,long double>> vec; for(int i = 1 ; i <= N ; i ++){ vec.pb(pair<long double,long double>((C[i]-A[i]*m)/B[i],-A[i]/B[i])); } sort(vec.begin(),vec.end()); if(inv(&vec)*2 <= N*(N-1)/2)r = m; else l = m; } return l; } int main(){ cout.precision(20); scanf("%d",&N); for(int i = 1 ; i <= N ; i ++){ cin >> A[i] >> B[i] >> C[i]; } long double X = sol(); for(int i = 1 ; i <= N ; i ++){ swap(A[i],B[i]); } long double Y = sol(); cout << X << " " << Y << endl; }
Submission Info
Submission Time | |
---|---|
Task | E - CARtesian Coodinate |
User | yokozuna57 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1874 Byte |
Status | AC |
Exec Time | 1737 ms |
Memory | 8920 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:86:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&N); ^
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 | 1721 ms | 6984 KB |
02.txt | AC | 1710 ms | 6984 KB |
03.txt | AC | 1723 ms | 6984 KB |
04.txt | AC | 1737 ms | 6984 KB |
05.txt | AC | 1714 ms | 6984 KB |
06.txt | AC | 1714 ms | 6984 KB |
07.txt | AC | 1729 ms | 6984 KB |
08.txt | AC | 1706 ms | 6984 KB |
09.txt | AC | 1716 ms | 6984 KB |
10.txt | AC | 1709 ms | 6984 KB |
11.txt | AC | 1712 ms | 7000 KB |
12.txt | AC | 1720 ms | 6984 KB |
13.txt | AC | 1702 ms | 6984 KB |
14.txt | AC | 1710 ms | 8920 KB |
15.txt | AC | 1720 ms | 6984 KB |
16.txt | AC | 1716 ms | 6984 KB |
17.txt | AC | 1715 ms | 6984 KB |
18.txt | AC | 1707 ms | 6984 KB |
19.txt | AC | 1683 ms | 8616 KB |
20.txt | AC | 1710 ms | 6984 KB |
21.txt | AC | 1369 ms | 6984 KB |
22.txt | AC | 1359 ms | 6984 KB |
23.txt | AC | 1729 ms | 6984 KB |
24.txt | AC | 1678 ms | 8616 KB |
25.txt | AC | 1724 ms | 6984 KB |
26.txt | AC | 1735 ms | 6984 KB |
27.txt | AC | 5 ms | 512 KB |
28.txt | AC | 5 ms | 512 KB |
29.txt | AC | 5 ms | 512 KB |
30.txt | AC | 5 ms | 512 KB |
31.txt | AC | 5 ms | 512 KB |
32.txt | AC | 5 ms | 512 KB |
s1.txt | AC | 5 ms | 512 KB |
s2.txt | AC | 5 ms | 512 KB |
s3.txt | AC | 5 ms | 512 KB |