글 읽기 - 시간초과

robin1001 3년 전 0

백준님 코드를 참고해서 다시 작성했습니다

+ 게시판 글을 읽어보고 set에 저장될때 pair 에서 일어나는 문제점을 해결하기 위해 setCmp 를 새로 정의했습니다.

+ 같은 점들이 나타나면 0으로 출력하도록 하였습니다.

시간초과가 납니다... 어디가 잘못된 것일까요

#include <cstdio>
#include <utility>
#include <vector>
#include <set>
#include <math.h>
#include <algorithm>

using namespace std;

struct setCmp {
	bool operator() (const pair<int, int> &a, const  pair<int, int> &b) const
	{
		if (a.second == b.second) {
			return a.first < b.first;
		}
		else {
			return a.second < b.second;
		}
	}
};

bool cmp_x(const pair<int,int> &u, const pair<int,int> &v) {
    return u.first < v.first;
}

bool cmp_y(const pair<int,int> &u, const pair<int,int> &v) {
    return u.second < v.second;
}

int dist(pair<int,int> p1, pair<int,int> p2) {
    return (p1.first-p2.first)*(p1.first-p2.first) + (p1.second-p2.second)*(p1.second-p2.second);
}

int main(){
  int n ; scanf("%d",&n);
  vector < pair<int,int> > a(n);
  for(int i=0; i<n; i++){
    int x, y;scanf("%d %d",&x,&y);
    a[i] = make_pair(x,y);
  }
  sort(a.begin(), a.end(), cmp_x);
  set<pair<int,int>, setCmp> cand;
  //printf(" cand size : %d\n",cand.size());
  cand.insert(a[0]);
  cand.insert(a[1]);
  int ans = dist(a[0], a[1]);
  for(int i=2; i<a.size(); i++){
    auto now = a[i];
    if(ans==0) break;
    //printf("now : %d %d (%d)\n",now.first, now.second,ans);
    // x좌표에서부터 거리가 d 인것
    for(int j=0; j<i; j++){
      auto p = a[j];
      int x = now.first - p.first;
      //printf(" -> xp:(%d,%d) , %d : %d\n", p.first, p.second, x*x, ans);
      //printf(" cand size : %d\n",cand.size());
      if((x*x) > ans){
        cand.erase(p);
      }
      else break;
    }
    // y좌표에서부터 거리가 d 인것
    int d = (int)sqrt((double)ans) + 1;
    auto lower = cand.lower_bound(make_pair(-100000,now.second - d));
    auto upper = cand.upper_bound(make_pair(100000,now.second + d));
    //printf(" lower : (%d,%d) / upper : (%d,%d)\n",(*lower).first, (*lower).second, (*upper).first, (*upper).second);
    for (auto it = lower; it != upper; it++) {
      int d = dist(now, *it);
      //printf(" -> yp:(%d,%d) , %d\n", (*it).first, (*it).second, d);
      if (d < ans) ans = d;
    }
    cand.insert(now);
  }
  printf("%d\n",ans);
  return 0;
}

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

문제

문제

출처

ICPC

시간초과

robin1001 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말