結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
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;
    }
    // 固定缩放因子，使得 a, b 满足 |a|,|b|<=1e5
    const int R = 100000;
    // 尝试候选方向次数（随机求解）
    const int candCount = 300;
    random_device rd;
    mt19937 gen(rd());
    uniform_real_distribution<double> dist(0, M_PI);
    
    for (int i = 0; i < candCount; i++){
        double phi = dist(gen);
        int a = (int)round(R * cos(phi));
        int b = (int)round(R * sin(phi));
        if(a == 0 && b == 0) continue;
        
        // 计算所有点在方向 (a,b) 上的投影值 V = a*x + b*y
        vector<long long> V(total);
        for (int j = 0; j < total; j++){
            V[j] = (long long)a * pts[j].x + (long long)b * pts[j].y;
        }
        // 利用 nth_element 快速求出排序后第 N-1 和第 N 个数
        // 这里下标从0开始，第 N 个点对应下标 N-1，(N+1)th对应下标 N
        vector<long long> temp = V; //复制一份，不破坏原数组
        nth_element(temp.begin(), temp.begin() + (N-1), temp.end());
        long long lower = temp[N-1];
        nth_element(temp.begin(), temp.begin() + N, temp.end());
        long long upper = temp[N];
        long long gap = upper - lower;
        // 情形1：gap >= 2，可直接选择 t = lower+1
        if(gap >= 2){
            int t = (int)(lower + 1);
            cout << a << " " << b << " " << -t << "\n";
            return 0;
        }
        // 情形2：gap == 1，则考虑乘2的方案，但要求 |a|,|b| <= 50000
        else if(gap == 1){
            if(abs(a) <= 50000 && abs(b) <= 50000){
                int tprime = (int)(2*lower + 1);
                cout << 2 * a << " " << 2 * b << " " << -tprime << "\n";
                return 0;
            }
        }
    }
    // 理论上必定存在解，万一候选方向全部失效，则输出默认直线（不会到这一步）
    cout << "1 0 0\n";
    return 0;
}
0