Submission #1642764
Source Code Expand
#include <algorithm> #include <cassert> #include <cstdlib> #include <ctime> #include <deque> #include <iostream> #include <map> #include <memory.h> #include <random> #include <set> #include <stdint.h> #include <vector> using namespace std; typedef pair<pair<int, int>, int> line; template <typename T> pair<T, T> cross(const line& l1, const line& l2) { const int a1 = l1.first.first; const int b1 = l1.first.second; const int c1 = l1.second; const int a2 = l2.first.first; const int b2 = l2.first.second; const int c2 = l2.second; const T x = (T)(c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1); const T y = (T)(c1 * a2 - c2 * a1) / (b1 * a2 - b2 * a1); return make_pair(x, y); } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector<line> vs(n); for (auto& p : vs) { cin >> p.first.first >> p.first.second >> p.second; } mt19937 rng(time(nullptr)); uniform_int_distribution<int> dist(0, n - 1); vector<double> xs, ys; const int SAMPLES = 500000; for (int t = 0; t < SAMPLES; t++) { _rep: int i = dist(rng); int j = dist(rng); if (i == j) goto _rep; auto p = cross<double>(vs[i], vs[j]); xs.push_back(p.first); ys.push_back(p.second); } sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end()); double d_lo_x = xs[SAMPLES / 2 - SAMPLES / 500]; double d_hi_x = xs[SAMPLES / 2 + SAMPLES / 500]; double d_lo_y = ys[SAMPLES / 2 - SAMPLES / 500]; double d_hi_y = ys[SAMPLES / 2 + SAMPLES / 500]; bool determ_x = (d_lo_x == d_hi_x); bool determ_y = (d_lo_y == d_hi_y); float lo_x = d_lo_x; float hi_x = d_hi_x; float lo_y = d_lo_y; float hi_y = d_hi_y; int lo_cnt_x = 0; int lo_cnt_y = 0; vector<double> rxs, rys; static int fs[40000]; for (int i = 0; i < n; i++) { line a = vs[i]; #pragma clang loop vectorize(enable) for (int j = i + 1; j < n; j++) { const auto p = cross<float>(a, vs[j]); if (p.first < lo_x) lo_cnt_x++; if (p.second < lo_y) lo_cnt_y++; fs[j] = (lo_x <= p.first && p.first <= hi_x ? 1 : 0) | (lo_y <= p.second && p.second <= hi_y ? 2 : 0); } if (!determ_x) { for (int j = i + 1; j < n; j++) { if (fs[j] & 1) { rxs.push_back(cross<double>(vs[i], vs[j]).first); } } } if (!determ_y) { for (int j = i + 1; j < n; j++) { if (fs[j] & 2) { rys.push_back(cross<double>(vs[i], vs[j]).second); } } } } int nn = (n * (n - 1) / 2 + 1) / 2; // cerr << lo_cnt_x << " + " << rxs.size() << " = " << lo_cnt_x + rxs.size() << " ~ " << nn << endl; // cerr << lo_cnt_y << " + " << rys.size() << " = " << lo_cnt_y + rys.size() << " ~ " << nn << endl; assert(determ_x || (lo_cnt_x < nn && lo_cnt_x + rxs.size() >= nn)); assert(determ_y || (lo_cnt_y < nn && lo_cnt_y + rys.size() >= nn)); if (!determ_x) nth_element(rxs.begin(), rxs.begin() + (nn - 1 - lo_cnt_x), rxs.end()); if (!determ_y) nth_element(rys.begin(), rys.begin() + (nn - 1 - lo_cnt_y), rys.end()); printf("%.12f %.12f\n", determ_x ? d_lo_x : rxs[nn - 1 - lo_cnt_x], determ_y ? d_lo_y : rys[nn - 1 - lo_cnt_y]); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - CARtesian Coodinate |
User | tanakh |
Language | C++14 (Clang 3.8.0) |
Score | 800 |
Code Size | 3646 Byte |
Status | AC |
Exec Time | 4913 ms |
Memory | 70344 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 | 4905 ms | 69192 KB |
02.txt | AC | 4897 ms | 61468 KB |
03.txt | AC | 4913 ms | 63772 KB |
04.txt | AC | 4892 ms | 60680 KB |
05.txt | AC | 4899 ms | 60788 KB |
06.txt | AC | 4872 ms | 60876 KB |
07.txt | AC | 4906 ms | 70344 KB |
08.txt | AC | 4904 ms | 68300 KB |
09.txt | AC | 4882 ms | 60880 KB |
10.txt | AC | 4890 ms | 67404 KB |
11.txt | AC | 4903 ms | 61456 KB |
12.txt | AC | 4899 ms | 68812 KB |
13.txt | AC | 4905 ms | 69448 KB |
14.txt | AC | 4902 ms | 61912 KB |
15.txt | AC | 4889 ms | 61600 KB |
16.txt | AC | 4906 ms | 68940 KB |
17.txt | AC | 4902 ms | 68044 KB |
18.txt | AC | 4909 ms | 61156 KB |
19.txt | AC | 4892 ms | 60960 KB |
20.txt | AC | 4897 ms | 59764 KB |
21.txt | AC | 3410 ms | 10972 KB |
22.txt | AC | 3408 ms | 8924 KB |
23.txt | AC | 4885 ms | 66508 KB |
24.txt | AC | 4883 ms | 65484 KB |
25.txt | AC | 4876 ms | 66892 KB |
26.txt | AC | 4884 ms | 61020 KB |
27.txt | AC | 111 ms | 8800 KB |
28.txt | AC | 104 ms | 8284 KB |
29.txt | AC | 111 ms | 8284 KB |
30.txt | AC | 88 ms | 8284 KB |
31.txt | AC | 78 ms | 10336 KB |
32.txt | AC | 111 ms | 8284 KB |
s1.txt | AC | 105 ms | 8284 KB |
s2.txt | AC | 87 ms | 8284 KB |
s3.txt | AC | 89 ms | 8284 KB |