회로판 위의 배터리 / SCPC 1차 예선

문제

해결

• 최대 전원거리는 $최대 Chebyshev / 2$
• LineA -> LineB의 최대 Chebyshev 거리를 구하되, 기준이 되는 점을 따로 잡아야 함
  • LineA의 pt1 -> 나머지Line들의 Chebyshev 거리의 최댓값 = ChebyshevA
  • LineA의 pt2 -> 나머지Line들의 Chebyshev 거리의 최댓값 = ChebyshevB
  • LineA -> 나머지Line 에 대한 전원거리는 $min(ChebyshevA / 2, ChebyshevB / 2)$
• $O(N^2)$

소스코드

/*
    Prob
    SCPC 1회 예선 
    회로판 위의 배터리
    Writer
    MyungSeung Kim(mskim9967@gmail.com)
*/

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

int tc, n;
struct Pt{
  int x, y;
  Pt(int _x, int _y): x(_x), y(_y){}

};
struct Line{
  Pt pt1, pt2;
  Line(Pt _pt1, Pt _pt2): pt1(_pt1), pt2(_pt2){}
};

void solve() {
  vector<Line> lines;
  int mmax = 0;

  cin >> n;
  for(int i = 0; i < n; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    lines.push_back(Line(Pt(x1, y1), Pt(x2, y2)));
  }

  for(Line lineA : lines) {
    int chebyshevA = 0, chebyshevB = 0;
    for(Line lineB : lines) {
      // chebyshevA: lineA pt1 -> 나머지 line들의 Chebyshev 거리의 최댓값
      chebyshevA = max(chebyshevA, min( 
        max(abs(lineA.pt1.x - lineB.pt1.x), abs(lineA.pt1.y - lineB.pt1.y)),
        max(abs(lineA.pt1.x - lineB.pt2.x), abs(lineA.pt1.y - lineB.pt2.y))
      ));
      // chebyshevB: lineA pt2 -> 나머지 line들의 Chebyshev 거리의 최댓값
      chebyshevB = max(chebyshevB, min(
        max(abs(lineA.pt2.x - lineB.pt2.x), abs(lineA.pt2.y - lineB.pt2.y)),
        max(abs(lineA.pt2.x - lineB.pt1.x), abs(lineA.pt2.y - lineB.pt1.y))
      ));
    }
    // mmax: 최대전원거리
    mmax = max(mmax, min(chebyshevA, chebyshevB));
  }

  if(mmax % 2) cout << mmax / 2.0 << '\n';
  else cout << mmax / 2 << '\n';
}

int main(void) {
  freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(0); cout << fixed; cout.precision(1);

  cin >> tc;
  for(int tt = 1; tt <= tc; tt++) {
    cout << "Case #" << tt << "\n";
    solve();
  }
  return 0;
}