Submission #2640401
Source Code Expand
#include<iostream>
#include<vector>
#include<algorithm>
#include <stdlib.h>
using namespace std;
int count_inversions(int n, vector<pair<double, int > > p) {
int res = 0;
vector<int> s(n+1, 0);
for(int k=0; k < n; k++) {
int c = 0;
int u = p[k].second;
while(u > 0) {
c += s[u];
u -= u & (-u);
}
u = p[k].second;
while(u <= n) {
s[u]++;
u += u & (-u);
}
res += k - c;
}
return res;
}
double find_median(int n, vector<int> a, vector<int> b, vector<int> c) {
int m = n * (n - 1) / 2, target_inversions;
if (m % 2 == 1)
target_inversions = (m - 1) / 2;
else
target_inversions = m / 2 - 1;
vector<pair<double, int> > slope(n);
for(int i=0; i < n; i++) {
slope[i] = {-a[i] * 1.0 / b[i], i};
}
sort(slope.begin(), slope.end());
vector<pair<double, int> > p(n);
double inf = 1e9;
double sa = -inf, sb = inf, s;
int n_steps = 300;
for(int step=0; step < n_steps; step++) {
s = (sa+sb) / 2;
for(int i=0; i < n; i++) {
int j = slope[i].second;
p[i] = {(-a[j] * s + c[j]) / b[j], i + 1};
}
sort(p.rbegin(), p.rend());
int c = count_inversions(n, p);
if (c > target_inversions) {
sb = s;
}
else {
sa = s;
}
}
return sa;
}
double find_median_exhaustive(int n, vector<int> a, vector<int> b, vector<int> c) {
int m = n * (n - 1) / 2, p;
if (m % 2 == 1)
p = (m - 1) / 2;
else
p = m / 2 - 1;
vector<double> t(m);
int k=0;
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
double d, dx, dy;
d = a[i] * b[j] - a[j] * b[i];
dx = c[i] * b[j] - c[j] * b[i];
dy = a[i] * c[j] - a[j] * c[i];
t[k] = dx / d;
// cout << "\t" << k << "\t" << t[k] << endl;
k += 1;
}
}
// for(int k=0; k<m; k++) {
// cout << "\t" << k << "\t" << t[k] << endl;
// }
// cout << endl;
sort(t.begin(), t.end());
return t[p];
}
int solve() {
int n;
cin >> n;
vector<int> a(n), b(n), c(n);
for(int i=0; i<n; i++)
cin >> a[i] >> b[i] >> c[i];
double x, y;
x = find_median(n, a, b, c);
y = find_median(n, b, a, c);
// y = find_median_exhaustive(n, b, a, c);
cout.precision(12);
cout << x << " " << y << endl;
return 0;
}
int check() {
srand (1);
int n_steps = 10;
for(int step = 0; step < n_steps ; step ++) {
int n = 10000;
int n_max = 100000 ;
vector<int> a(n), b(n), c(n);
for(int i=0; i<n; i++) a[i] = rand() % (2 * n_max) - n_max;
for(int i=0; i<n; i++) b[i] = rand() % (2 * n_max) - n_max;
for(int i=0; i<n; i++) c[i] = rand() % (2 * n_max) - n_max;
double x = find_median(n, a, b, c);
double y = find_median(n, a, b, c);
cout << x << " " << y << " " << x - y << endl;
}
}
int main() {
solve();
// check();
}
Submission Info
Submission Time |
|
Task |
E - CARtesian Coodinate |
User |
Martial |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
3294 Byte |
Status |
AC |
Exec Time |
2589 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 |
2559 ms |
3236 KB |
02.txt |
AC |
2537 ms |
3236 KB |
03.txt |
AC |
2541 ms |
3236 KB |
04.txt |
AC |
2510 ms |
3236 KB |
05.txt |
AC |
2565 ms |
3236 KB |
06.txt |
AC |
2553 ms |
3236 KB |
07.txt |
AC |
2560 ms |
3236 KB |
08.txt |
AC |
2561 ms |
3236 KB |
09.txt |
AC |
2581 ms |
3236 KB |
10.txt |
AC |
2528 ms |
3236 KB |
11.txt |
AC |
2537 ms |
3236 KB |
12.txt |
AC |
2562 ms |
3236 KB |
13.txt |
AC |
2550 ms |
3236 KB |
14.txt |
AC |
2539 ms |
3236 KB |
15.txt |
AC |
2556 ms |
3236 KB |
16.txt |
AC |
2523 ms |
3236 KB |
17.txt |
AC |
2581 ms |
3236 KB |
18.txt |
AC |
2531 ms |
3236 KB |
19.txt |
AC |
2589 ms |
3236 KB |
20.txt |
AC |
2537 ms |
3236 KB |
21.txt |
AC |
1110 ms |
3236 KB |
22.txt |
AC |
1110 ms |
3236 KB |
23.txt |
AC |
2552 ms |
3236 KB |
24.txt |
AC |
2556 ms |
3236 KB |
25.txt |
AC |
2569 ms |
3236 KB |
26.txt |
AC |
2560 ms |
3236 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 |