Submission #1813790
Source Code Expand
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
typedef int VAL;
const int MAX_B = 610000;
int SIZE_B;
struct BIT {
VAL dat[MAX_B + 1];
void init(int n = 1) {
SIZE_B = n;
for (int i = 0; i <= SIZE_B; ++i) dat[i] = 0;
}
inline void add(int a, VAL x) {
for (int i = a; i <= SIZE_B; i += i & -i)
dat[i] = dat[i] + x;
}
inline VAL sum(int a) {
VAL res = 0;
for (int i = a; i > 0; i -= i & -i)
res = res + dat[i];
return res;
}
inline VAL sum(int a, int b) {
return sum(b - 1) - sum(a - 1);
}
void print() {
for (int i = 1; i <= SIZE_B; ++i) cout << sum(i, i + 1) << ",";
cout << endl;
}
};
BIT bit;
int N;
const int MAX = 510000;
typedef pair<pair<double,double>, double> LINE;
vector<LINE> lines;
bool cmpx(LINE a, LINE b) {
return -a.first.first / a.first.second > -b.first.first / b.first.second;
}
bool cmpy(LINE a, LINE b) {
return -a.first.second / a.first.first > -b.first.second / b.first.first;
}
double inter[MAX];
map<double,int> ma;
int id[MAX];
double solve(bool isx) {
if (isx) sort(lines.begin(), lines.end(), cmpx);
else sort(lines.begin(), lines.end(), cmpy);
//COUT(lines);
double lo = -(1LL<<30), hi = 1LL<<30;
for (int iter = 0; iter < 100; ++iter) {
double mid = (lo + hi) / 2;
ma.clear();
for (int i = 0; i < N; ++i) {
LINE line = lines[i];
double po = 0;
if (isx) po = (line.second - line.first.first*mid) / line.first.second;
else po = (line.second - line.first.second*mid) / line.first.first;
inter[i] = po;
ma[po] = 0;
}
int co = 0;
for (map<double,int>::iterator it = ma.begin(); it != ma.end(); ++it) {
it->second = co++;
}
for (int i = 0; i < N; ++i) {
id[i] = ma[inter[i]];
//cout << i << ": " << lines[i] << ", " << "(" << mid << ")" << inter[i] << "; " << id[i] << endl;
}
int count = 0;
bit.init(N+5);
for (int i = 0; i < N; ++i) {
int add = id[i];
int tmp = bit.sum(add+2, N+3);
count += tmp;
bit.add(add+1, 1);
}
int aida = (N*(N-1)/2 - 1)/2;
if (count >= aida + 1) hi = mid;
else lo = mid;
//cout << mid << ": " << ", " << aida << ": " << count << endl;
}
return hi;
}
int main() {
while (cin >> N) {
lines.resize(N);
for (int i = 0; i < N; ++i) {
cin >> lines[i].first.first >> lines[i].first.second >> lines[i].second;
}
double X = solve(true);
double Y = solve(false);
cout << fixed << setprecision(10) << X << " " << Y << endl;
}
}
Submission Info
Submission Time |
|
Task |
E - CARtesian Coodinate |
User |
drken |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
3927 Byte |
Status |
AC |
Exec Time |
3946 ms |
Memory |
12032 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 |
3858 ms |
9984 KB |
02.txt |
AC |
3830 ms |
9984 KB |
03.txt |
AC |
3858 ms |
9984 KB |
04.txt |
AC |
3853 ms |
9984 KB |
05.txt |
AC |
3828 ms |
9984 KB |
06.txt |
AC |
3843 ms |
9984 KB |
07.txt |
AC |
3839 ms |
9984 KB |
08.txt |
AC |
3874 ms |
9984 KB |
09.txt |
AC |
3866 ms |
9984 KB |
10.txt |
AC |
3844 ms |
9984 KB |
11.txt |
AC |
3839 ms |
10112 KB |
12.txt |
AC |
3832 ms |
9984 KB |
13.txt |
AC |
3878 ms |
9984 KB |
14.txt |
AC |
3854 ms |
9984 KB |
15.txt |
AC |
3849 ms |
9984 KB |
16.txt |
AC |
3851 ms |
9984 KB |
17.txt |
AC |
3833 ms |
9984 KB |
18.txt |
AC |
3864 ms |
9984 KB |
19.txt |
AC |
3844 ms |
9984 KB |
20.txt |
AC |
3845 ms |
9984 KB |
21.txt |
AC |
2589 ms |
12032 KB |
22.txt |
AC |
2739 ms |
9984 KB |
23.txt |
AC |
3946 ms |
9984 KB |
24.txt |
AC |
3935 ms |
9984 KB |
25.txt |
AC |
3927 ms |
9984 KB |
26.txt |
AC |
3787 ms |
12032 KB |
27.txt |
AC |
2 ms |
2304 KB |
28.txt |
AC |
2 ms |
2304 KB |
29.txt |
AC |
2 ms |
2304 KB |
30.txt |
AC |
2 ms |
2304 KB |
31.txt |
AC |
2 ms |
2304 KB |
32.txt |
AC |
2 ms |
2304 KB |
s1.txt |
AC |
2 ms |
2304 KB |
s2.txt |
AC |
2 ms |
2304 KB |
s3.txt |
AC |
2 ms |
2304 KB |