結果

問題 No.1265 Balloon Survival
コンテスト
ユーザー keymoon
提出日時 2020-10-23 23:30:54
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 1,813 bytes
コンパイル時間 3,037 ms
コンパイル使用メモリ 110,208 KB
実行使用メモリ 24,320 KB
最終ジャッジ日時 2024-07-21 13:27:29
合計ジャッジ時間 10,315 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 TLE * 1 -- * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Data.SqlTypes;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
public static class P
{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        long[][] pts = Enumerable.Repeat(0, n).Select(_ => Console.ReadLine().Split().Select(long.Parse).ToArray()).ToArray();
        List<int> remain = Enumerable.Range(0, n).ToList();
        int res = 0;
        int curSquareT = 0;
        while (remain.Count > 1)
        {
            long valid = curSquareT;
            long invalid = long.MaxValue;
            while (invalid - valid > 1)
            {
                var mid = (invalid + valid) / 2;
                for (int i = 0; i < remain.Count; i++)
                    for (int j = i + 1; j < remain.Count; j++)
                        if (GetDist(pts[remain[i]], pts[remain[j]]) <= mid) goto inv;
                valid = mid;
                continue;
                inv:;
                invalid = mid;
            }

            for (int i = 0; i < remain.Count; i++)
                for (int j = i + 1; j < remain.Count; j++)
                    if (GetDist(pts[remain[i]], pts[remain[j]]) == invalid)
                    {
                        remain.RemoveAt(j);
                        if (i != 0) remain.RemoveAt(i);
                        else res++;
                        goto end;
                    }
            end:;
        }
        Console.WriteLine(res);
    }

    static long GetDist(long[] a, long[] b)
    {
        var dy = a[0] - b[0];
        var dx = a[1] - b[1];
        return dy * dy + dx * dx;
    }
}
0