結果

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

ソースコード

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;
    }
    // 尝试竖直直线：按 x 轴排序（当 x 相同时按 y 排序）
    {
        vector<Point> temp = pts;
        sort(temp.begin(), temp.end(), [](const Point &a, const Point &b){
            return a.x == b.x ? a.y < b.y : a.x < b.x;
        });
        int x_low = temp[N-1].x, x_high = temp[N].x;
        if(x_low < x_high){
            // 若能选整数 t 满足 x_low < t < x_high
            if(x_low + 1 < x_high){
                int t = x_low + 1;
                cout << 1 << " " << 0 << " " << -t << "\n";
                return 0;
            } else {
                // x_low 与 x_high 连续，取 t = (2*x_low + 1)/2, 即输出 2x - (2*x_low+1)=0
                int t = 2 * x_low + 1;
                cout << 2 << " " << 0 << " " << -t << "\n";
                return 0;
            }
        }
    }
    // 竖直直线失败则尝试水平直线：按 y 轴排序（当 y 相同时按 x 排序）
    {
        vector<Point> temp = pts;
        sort(temp.begin(), temp.end(), [](const Point &a, const Point &b){
            return a.y == b.y ? a.x < b.x : a.y < b.y;
        });
        int y_low = temp[N-1].y, y_high = temp[N].y;
        if(y_low < y_high){
            if(y_low + 1 < y_high){
                int t = y_low + 1;
                cout << 0 << " " << 1 << " " << -t << "\n";
                return 0;
            } else {
                int t = 2 * y_low + 1;
                cout << 0 << " " << 2 << " " << -t << "\n";
                return 0;
            }
        }
    }
    // 若以上两种均不行，则尝试以斜率1构造直线：令 s = x+y
    {
        vector<long long> s(total);
        for (int i = 0; i < total; i++){
            s[i] = (long long)pts[i].x + pts[i].y;
        }
        sort(s.begin(), s.end());
        long long s_low = s[N-1], s_high = s[N];
        if(s_low < s_high){
            if(s_low + 1 < s_high){
                long long t = s_low + 1;
                cout << 1 << " " << 1 << " " << -t << "\n";
                return 0;
            } else {
                long long t = 2 * s_low + 1;
                cout << 2 << " " << 2 << " " << -t << "\n";
                return 0;
            }
        }
    }
    // 最后尝试以斜率 -1 构造直线：令 d = x-y
    {
        vector<long long> d(total);
        for (int i = 0; i < total; i++){
            d[i] = (long long)pts[i].x - pts[i].y;
        }
        sort(d.begin(), d.end());
        long long d_low = d[N-1], d_high = d[N];
        if(d_low < d_high){
            if(d_low + 1 < d_high){
                long long t = d_low + 1;
                cout << 1 << " " << -1 << " " << -t << "\n";
                return 0;
            } else {
                long long t = 2 * d_low + 1;
                cout << 2 << " " << -2 << " " << -t << "\n";
                return 0;
            }
        }
    }
    // 若万一都不行，输出一个默认直线（其实理论上不会到这一步）
    cout << "1 0 0\n";
    return 0;
}
0