글 읽기 - 2585 경비행기 반례 하나만 찾아주실수있으신가요

dlftls38 4년 전 0

제출시 33%까지 맞고 틀리는데

10000,10000까지의 거리가 짧은 노드 순으로 정렬해서 연료통을 이분탐색하며 k이내로 가능한 경우를 찾도록 구현했는데

여러 예제케이스를 해봤을땐 다 되는거같은데

반례 하나만 찾아주실수있으신가요?

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <limits.h>
#include <functional>
#include <math.h>
using namespace std;
int dist(int x1,int y1,int x2,int y2){
	int temp = ceil(sqrt(pow(x1-x2,2)+pow(y1-y2,2)));
	if(temp%10){
		return temp/10+1;
	}
	else{
		return temp/10;
	}
}
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	int i,j;
	vector<pair<int,int> >temp;
	temp.push_back(make_pair(0,0));
	for(i=0;i<n;i++){
		int q,w;
		scanf("%d%d",&q,&w);
		temp.push_back(make_pair(q,w));	
	}
	temp.push_back(make_pair(10000,10000));
	vector<pair<pair<int,int>, int> >v[1002];
	for(i=0;i<n+2;i++){
		for(j=0;j<n+2;j++){
			v[i].push_back(make_pair(make_pair(dist(temp[j].first,temp[j].second,10000,10000),dist(temp[j].first,temp[j].second,temp[i].first,temp[i].second)),j));
		}
		sort(v[i].begin(),v[i].end());
//		for(j=0;j<n+2;j++){
//			printf("%d %d %d\n",v[i][j].first.first,v[i][j].first.second,v[i][j].second);
//		}
	}
	int l=0;
	int r=1500;
	int mid;
	int ans;
	while(l<=r){
		mid=(l+r)/2;
		int count=-1;
		int pos=0;
		int dis=1500;
		while(1){
			int check=0;
			for(i=0;i<n+2;i++){
				if(v[pos][i].first.second<=mid && v[pos][i].first.first<dis){
					count++;
					pos=v[pos][i].second;
					dis=v[pos][i].first.first;
					check=1;
					break;
				}
			}
			if(dis==0 || check==0){
				break;
			}
		}
		if(count<=k && dis==0){
			r=mid-1;
			ans=mid;
		}
		else{
			l=mid+1;
		}
	}
	printf("%d",ans);
}

juno13 4년 전 0

너무 늦은 답변인지는 모르겠습니다.

13줄 dist함수가 오류가 생길 수 있을것같습니다.

ceil(sqrt(pow(x1-x2,2)+pow(y1-y2,2)))이 대충 10.1이었다고 치면 연료는 2 l가 필요한데

이 함수는 1을 리턴할 것 같습니다.

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

문제

문제

출처

ICPC

2585 경비행기 반례 하나만 찾아주실수있으신가요

dlftls38 4년 전 0

juno13 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말