[백준 5205] School Colors (C#, C++) - soo:bak

문제 링크

5205번 - School Colors

설명

대비가 최대가 되는 모든 색상 쌍의 인덱스를 구하는 문제입니다.

모든 쌍의 거리를 비교해 최댓값과 같은 쌍을 모으면 답이 됩니다.

접근법

먼저 모든 색상 쌍을 만들어 대비를 계산합니다.

최댓값이 되는 쌍이 여러 개일 수 있으므로, 현재 최댓값보다 크면 목록을 비우고 다시 담는 방식이 자연스럽습니다.

다음으로 거리의 제곱값을 비교하고, 문제의 인덱스 규칙에 맞게 1부터 출력합니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

class fastscanner {
  private readonly StreamReader _reader;
  private string[] _tokens = Array.Empty<string>();
  private int _index = 0;

  public fastscanner(StreamReader reader) {
    _reader = reader;
  }

  public int nextint() {
    while (_index >= _tokens.Length) {
      var line = _reader.ReadLine();
      if (line == null) {
        return 0;
      }
      _tokens = line.Split(' ', StringSplitOptions.RemoveEmptyEntries);
      _index = 0;
    }
    var value = int.Parse(_tokens[_index]);
    _index++;
    return value;
  }
}

class Program {
  static void Main() {
    using var reader = new StreamReader(Console.OpenStandardInput());
    using var writer = new StreamWriter(Console.OpenStandardOutput());
    var fs = new fastscanner(reader);
    var k = fs.nextint();
    var sb = new StringBuilder();
    for (var ds = 1; ds <= k; ds++) {
      var n = fs.nextint();
      var colors = new (int r, int g, int b)[n];
      for (var i = 0; i < n; i++) {
        var r = fs.nextint();
        var g = fs.nextint();
        var b = fs.nextint();
        colors[i] = (r, g, b);
      }

      var best = -1L;
      var pairs = new List<(int, int)>();
      for (var i = 0; i < n; i++) {
        for (var j = i + 1; j < n; j++) {
          var dr = colors[i].r - colors[j].r;
          var dg = colors[i].g - colors[j].g;
          var db = colors[i].b - colors[j].b;
          var dist2 = 1L * dr * dr + 1L * dg * dg + 1L * db * db;
          if (dist2 > best) {
            best = dist2;
            pairs.Clear();
            pairs.Add((i + 1, j + 1));
          } else if (dist2 == best) {
            pairs.Add((i + 1, j + 1));
          }
        }
      }

      sb.Append("Data Set ").Append(ds).Append(":\n");
      foreach (var (a, b) in pairs) {
        sb.Append(a).Append(' ').Append(b).Append('\n');
      }
    }
    writer.Write(sb.ToString());
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int k;
  cin >> k;
  for (int ds = 1; ds <= k; ds++) {
    int n;
    cin >> n;
    vector<array<int,3>> c(n);
    for (int i = 0; i < n; i++) {
      cin >> c[i][0] >> c[i][1] >> c[i][2];
    }

    ll best = -1;
    vp ans;
    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        ll dr = c[i][0] - c[j][0];
        ll dg = c[i][1] - c[j][1];
        ll db = c[i][2] - c[j][2];
        ll dist2 = dr * dr + dg * dg + db * db;
        if (dist2 > best) {
          best = dist2;
          ans.clear();
          ans.emplace_back(i + 1, j + 1);
        } else if (dist2 == best) {
          ans.emplace_back(i + 1, j + 1);
        }
      }
    }

    cout << "Data Set " << ds << ":\n";
    for (auto &p : ans) {
      cout << p.first << ' ' << p.second << "\n";
    }
  }

  return 0;
}