結果

問題 No.3074 Divide Points Fairly
コンテスト
ユーザー Zhiyuan Chen
提出日時 2025-03-28 22:34:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,083 bytes
コンパイル時間 2,192 ms
コンパイル使用メモリ 208,204 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-28 22:34:44
合計ジャッジ時間 5,935 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){
            if(x_low + 1 < x_high){
                int t = x_low + 1;
                cout << 1 << " " << 0 << " " << -t << "\n";
                return 0;
            } else {
                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