結果

問題 No.3074 Divide Points Fairly
コンテスト
ユーザー Zhiyuan Chen
提出日時 2025-03-28 22:40:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,945 bytes
コンパイル時間 2,285 ms
コンパイル使用メモリ 201,512 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-28 22:40:32
合計ジャッジ時間 7,298 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28 WA * 14
権限があれば一括ダウンロードができます

ソースコード

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;
    // 候选角数量，此处选100即可（区间[0,π)）
    const int candCount = 100;
    for (int i = 0; i < candCount; i++){
        // 取候选角 φ 在 [0, π) 均匀分布
        double phi = (double)i * M_PI / candCount;
        // 计算 a, b 取整
        int a = (int)round(R * cos(phi));
        int b = (int)round(R * sin(phi));
        if(a == 0 && b == 0) continue;
        
        // 对所有点计算投影值 V_i = a*x + b*y
        vector<int> V(total);
        for (int j = 0; j < total; j++){
            // 注意：由于 a,b,x,y 均为整数，V[i] 也是整数
            V[j] = a * pts[j].x + b * pts[j].y;
        }
        // 使用 nth_element 求第 N-1 和第 N 个最小值
        // 注意：下标从0开始，第 N 个点对应下标 N-1，(N+1)th对应下标 N
        vector<int> temp = V; //复制，避免破坏原数组
        nth_element(temp.begin(), temp.begin() + (N-1), temp.end());
        int lower = temp[N-1];
        nth_element(temp.begin(), temp.begin() + N, temp.end());
        int upper = temp[N];
        // 判断是否存在缺口：要求 lower < t < upper 有整数 t
        if(lower < upper && (upper - lower) >= 2){
            int t = lower + 1;  // 即选择 t，使得 lower < t < upper
            // 构造直线： a * x + b * y - t = 0  => c = -t
            cout << a << " " << b << " " << -t << "\n";
            return 0;
        }
    }
    // 理论上必有一方向可行，万一候选方向全部失效则输出默认直线
    cout << "1 0 0\n";
    return 0;
}
0