oj.uz

답안 #334609

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
334609 2020-12-09T15:00:37 Z GioChkhaidze Odašiljači (COCI20_odasiljaci) C++14
0 / 70
 1000 ms 4460 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=1e3+1;
int n,x[N],y[N],cnt;
bool f[N];
vector < int > v[N];

void Dfs(int x) {
	++cnt;
	f[x]=true;
	for (int i=0; i<v[x].size(); i++) {
		if (!f[v[x][i]]) Dfs(v[x][i]);
	}
}

bool check(long double d) {
	cnt=0;
	for (int i=1; i<=n; i++) {
		v[i].clear();
		f[i]=0;
	}
	
	for (int i=1; i<=n; i++)
		for (int j=1; j<i; j++)
			if (d*d>=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))
				v[i].pb(j),v[j].pb(i);
	
	Dfs(1);
	return (cnt==n);
}

main () {
	cin>>n;
	for (int i=1; i<=n; i++) {
		cin>>x[i]>>y[i];
	}
	
	long double l=0,r=1e10,mid,res=-1;
	for (int i=1; i<=1000; i++) {
		mid=(l+r)/2.0;
		if (check(mid))
			res=mid,r=mid-0.0000001;
				else
			l=mid+0.0000001;
	}
	res/=2.0;
	printf("%.7f",res);	
}

Compilation message

odasiljaci.cpp: In function 'void Dfs(int)':
odasiljaci.cpp:13:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i=0; i<v[x].size(); i++) {
      |                ~^~~~~~~~~~~~
odasiljaci.cpp: At global scope:
odasiljaci.cpp:34:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main () {
      |       ^
odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:49:13: warning: format '%f' expects argument of type 'double', but argument 2 has type 'long double' [-Wformat=]
   49 |  printf("%.7f",res);
      |          ~~~^  ~~~
      |             |  |
      |             |  long double
      |             double
      |          %.7Lf

Subtask #1
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Incorrect 10 ms 364 KB Output isn't correct
4 Incorrect 36 ms 364 KB Output isn't correct
5 Incorrect 70 ms 364 KB Output isn't correct
6 Incorrect 587 ms 1516 KB Output isn't correct
7 Incorrect 622 ms 1388 KB Output isn't correct
8 Execution timed out 1084 ms 3436 KB Time limit exceeded
9 Execution timed out 1093 ms 4460 KB Time limit exceeded
10 Execution timed out 1047 ms 4460 KB Time limit exceeded