結果

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

ソースコード

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;
        
        // 计算所有点的投影值 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-index：第 N 个点下标 N-1，下一点下标 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];
        // 当存在 gap（要求 gap>=2，这样就能选择一个整数 t 避免落在某个点上）
        if(lower < upper && (upper - lower) >= 2){
            int t = (int)(lower + 1);
            cout << a << " " << b << " " << -t << "\n";
            return 0;
        }
    }
    // 理论上必定存在解，万一找不到则输出默认直线（不会到这一步）
    cout << "1 0 0\n";
    return 0;
}
0