結果

問題 No.869 ふたつの距離
コンテスト
ユーザー 梧桐
提出日時 2026-05-19 14:24:48
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 162 ms / 1,500 ms
コード長 1,940 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 808 ms
コンパイル使用メモリ 105,584 KB
実行使用メモリ 11,912 KB
最終ジャッジ日時 2026-05-19 14:25:01
合計ジャッジ時間 9,543 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 93
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:78:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   78 |     for (auto [x, y] : pts) printf("%.12Lf %.12Lf\n", x, y);
      |               ^
main.cpp:56:62: warning: 'v' may be used uninitialized [-Wmaybe-uninitialized]
   56 |     int au = (int) (1.0 * a * u * (u - 1) / (u * (u - 1) + v * (v - 1)) + 0.5);
      |                                                            ~~^~~~~~~~~
main.cpp:50:12: note: 'v' was declared here
   50 |     int u, v;
      |            ^

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <utility>
#include <vector>

using namespace std;

typedef long double LD;
typedef pair<LD, LD> PLD;

int n, a, b;

LD GetRandom() {
    int x = rand() % 10000;
    int y = rand() % 10000;
    return (x * 10000 + y) / 10000000000.0;
}

vector<LD> GenSeq(int sz, int tgt) {
    vector<LD> t;
    t.push_back(GetRandom());
    while ((int) t.size() < sz) {
        t.push_back(t.back() + GetRandom());
    }
    if (sz < 2) return t;
    LD lo = 0, hi = 17.3 / (sz - 1);
    for (int i = 0; i < 100; ++i) {
        LD mid = (lo + hi) / 2.0;
        int num = 0;
        for (int y = 0; y < sz; ++y) {
            for (int x = 0; x < y; ++x) {
                if ((t[y] + y * mid) - (t[x] + x * mid) <= 10) ++num;
            }
        }
        if (num >= tgt) lo = mid;
        else hi = mid;
    }
    for (int i = 0; i < sz; ++i) t[i] += lo * i;
    return t;
}

int main() {
    srand(time(NULL));
    scanf("%d%d%d", &n, &a, &b);

    int u, v;
    for (u = 1; u <= n; ++u) {
        v = n - u;
        if (u >= v && u * (u - 1) / 2 + v * (v - 1) / 2 >= a) break;
    }

    int au = (int) (1.0 * a * u * (u - 1) / (u * (u - 1) + v * (v - 1)) + 0.5);
    int av = a - au;
    b -= u * (u - 1) / 2 + v * (v - 1) / 2;

    vector<LD> su = GenSeq(u, au);
    vector<LD> sv = GenSeq(v, av);

    vector<double> thresholds;
    for (auto s : su) {
        for (auto t : sv) {
            thresholds.push_back(sqrt(400 - (t - s) * (t - s)) - 0.000000001);
        }
    }
    sort(thresholds.begin(), thresholds.end());
    reverse(thresholds.begin(), thresholds.end());

    double c = thresholds[b - 1];  // U组的 y 坐标

    vector<PLD> pts;
    for (auto s : su) pts.push_back({ s, c });
    for (auto t : sv) pts.push_back({ t, 0 });

    for (auto [x, y] : pts) printf("%.12Lf %.12Lf\n", x, y);

    return 0;
}
0