結果

問題 No.3074 Divide Points Fairly
ユーザー Zhiyuan Chen
提出日時 2025-03-29 12:34:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,542 bytes
コンパイル時間 2,429 ms
コンパイル使用メモリ 204,096 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-29 12:34:40
合計ジャッジ時間 8,003 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
 
const double PI = acos(-1);
 
struct Point {
    int x, y;
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    int total = 2 * N;
    vector<Point> pts(total);
    for (int i = 0; i < total; i++){
        cin >> pts[i].x >> pts[i].y;
    }
    
    // 固定尺度 D = 10^5
    const int D = 100000;
    // 随机生成角度 phi uniformly in [0, PI)
    random_device rd;
    mt19937 gen(rd());
    uniform_real_distribution<double> dist(0.0, PI);
    
    // 重复随机选取候选方向直到找到合适的 (a,b) 并由此确定合适的 c
    while(true){
        double phi = dist(gen);
        int a = (int)round(D * cos(phi));
        int b = (int)round(D * sin(phi));
        if(a == 0 && b == 0) continue;
 
        // 对所有点计算 f_i = a*x_i + b*y_i
        vector<long long> f(total);
        for (int i = 0; i < total; i++){
            f[i] = (long long)a * pts[i].x + (long long)b * pts[i].y;
        }
        sort(f.begin(), f.end());
 
        // 注意：下标从0开始，第 N 个最小值为 f[N-1]，第 N+1 个最小值为 f[N]。
        // 要保证存在整数 t 满足 f[N-1] < t < f[N]，即要求 f[N] - f[N-1] >= 2。
        if(f[N] - f[N-1] >= 2){
            int t = f[N-1] + 1; // 选择 t 为 f[N-1] + 1
            int c = -t;        // 则直线为 ax + by - t = 0，即 c = -t
            cout << a << " " << b << " " << c << "\n";
            return 0;
        }
    }
    
    return 0;
}
0