結果
問題 | No.3074 Divide Points Fairly |
ユーザー |
👑 |
提出日時 | 2025-02-14 17:32:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 1,398 bytes |
コンパイル時間 | 2,479 ms |
コンパイル使用メモリ | 199,280 KB |
実行使用メモリ | 7,328 KB |
最終ジャッジ日時 | 2025-03-27 12:51:26 |
合計ジャッジ時間 | 8,900 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int D = 100000; random_device seed; mt19937 mt(seed()); uniform_int_distribution dist(-D, D); int main(){ int n; cin >> n; vector<long long> x(2 * n), y(2 * n); for(int i = 0; i < 2 * n; i++) cin >> x[i] >> y[i]; // count points s.t. ax_i + by_i + c < 0 auto cnt_minus = [&](long long a, long long b, long long c){ int res = 0; for(int i = 0; i < 2 * n; i++) if(a * x[i] + b * y[i] + c < 0) res++; return res; }; // count points s.t. ax_i + by_i + c = 0 auto cnt_zero = [&](long long a, long long b, long long c){ int res = 0; for(int i = 0; i < 2 * n; i++) if(a * x[i] + b * y[i] + c == 0) res++; return res; }; auto solve = [&](long long a, long long b) -> pair<bool, long long>{ if(a == 0 and b == 0) return make_pair(false, 0LL); // ax_i + by_i + ok < 0: N or less points long long ok = +1001001001001; long long ng = -1001001001001; while(ok - ng > 1){ long long mid = (ng + ok) / 2; if(cnt_minus(a, b, mid) + cnt_zero(a, b, mid) <= n) ok = mid; else ng = mid; } if(cnt_minus(a, b, ok) == n and cnt_zero(a, b, ok) == 0) return make_pair(true, ok); else return make_pair(false, 0LL); }; while(true){ long long a = dist(mt), b = dist(mt); auto [success, c] = solve(a, b); if(success){ cout << a << ' ' << b << ' ' << c << "\n"; return 0; } } return 0; }