글 읽기 - 시간초과가 나옵니다 ㅜㅜ

joehandlebar 6년 전 0

채점 시작하기 전에 시간초과가 나와요, 제 기계에는 ~250ms 나오는데, 혹시 루프가 안 풀리는 데가 있으면..

#include <iostream>
#include <utility>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stdlib.h>

using namespace std;

typedef vector<pair<int,int>> coords;

bool by_x(pair<int,int> a, pair<int,int> b) {
  return a.first < b.first;
}

bool by_y(pair<int,int> a, pair<int,int> b) {
  return a.second < b.second;
}

int dist(pair<int,int> a, pair<int,int> b) {
  int x = a.first - b.first;
  int y = a.second - b.second;
  return x*x + y*y;
}

int closest_dist(int start, int end, coords &X, coords &Y) {
  if ((end - start) <= 3) {
    int d = 800000001;
    for (int i = start; i < end; i++) {
      for (int j = i + 1; j < end; j++) {
        d = min(d, dist(X[i],X[j]));
      }
    }
    return d;
  }
    
  int m = (end - start)/2;
  int mid = X[start+m].first;

  coords Yl; coords Yr;
  Yl.reserve(Y.size());
  Yr.reserve(Y.size());

  for (int i = 0; i < Y.size(); i++) {
    if (Y[i].first <= mid) {
      Yl.push_back(Y[i]);
    } else {
      Yr.push_back(Y[i]);
    }
  }

  coords Y_;
  Y_.reserve(Y.size());
  int dl = closest_dist(start,start+m,X,Yl);
  int dr = closest_dist(start+m,end,X,Yr);
  int d = min(dl,dr);

  for (int i = 0; i < Y.size(); i++) {
    if (abs(Y[i].first - mid) < d) {
      Y_.push_back(Y[i]);
    }
  }

  int d2;
  for (int i = 0; i < Y_.size(); i++) {
    for (int j = i+1; j < Y_.size() && (Y_[j].second - Y_[i].second < d); j++) {
      d2 = dist(Y_[i], Y_[j]);
      if (d2 < d) { d = d2; }
    }
  }

  return d;
}

coords X;
coords Y;

int main() {
  int n, x, y;
  scanf("%d", &n);
  X.reserve(n);
  Y.reserve(n);

  for (int i = 0; i < n; i++) {
    scanf("%d %d", &x, &y);
    X.push_back(make_pair(x, y));
    Y.push_back(make_pair(x, y));
  }

  sort(X.begin(),X.end(),by_x);
  sort(Y.begin(),Y.end(),by_y);

  int result = closest_dist(0,X.size(),X,Y);

  cout << result << '\n';

  return 0;
}

jh05013 6년 전 0

점이 10만개까지 될 수 있어서 N²알고리즘으로는 시간 내에 풀 수 없습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 나옵니다 ㅜㅜ

joehandlebar 6년 전 0

jh05013 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말