oj.uz

Submission #56126

# Submission time Handle Problem Language Result Execution time Memory
56126 2018-07-10T05:10:06 Z 정원준(#1583) Mobile (BOI12_mobile) C++11
0 / 100
 67 ms 3312 KB 
#include <bits/stdc++.h>
#define L long long

using namespace std;

L n,l;

struct S{
	L x,y;
}a[100010];

bool operator<(S a,S b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}

S st[100010];
L top;

double cross(S a,S b){
	return (double)(b.x*b.x-a.x*a.x+
					 b.y*b.y-a.y*a.y)/(2*(b.x-a.x));

}

bool shellpop(S temp){
	if(top<2) return 0;
	double cross1=cross(st[top],st[top-1]);
	top++;
	st[top]=temp;
	double cross2=cross(st[top],st[top-1]);
	top--;
	return cross2<cross1;
}

double ans;

int main()
{
	scanf("%lld %lld",&n,&l);
	L i;
	for(i=1;i<=n;i++)
	{
		scanf("%lld %lld",&a[i].x,&a[i].y);
		if(a[i].y<0) a[i].y*=-1;
	}
	sort(a+1,a+n+1);
	for(i=1;i<=n;i++)
	{
		if(i<n&&a[i].x==a[i+1].x) continue;
		if(top<2)
		{
			top++;
			st[top]=a[i];
		}
		else
		{
			while(shellpop(a[i])) top--;
			top++;
			st[top]=a[i];
		}
	}
	if(top==1)
	{
		printf("%lf",max(sqrt(st[1].x*st[1].x+st[1].y*st[1].x),sqrt((st[1].x-l)*(st[1].x-l)+st[1].y*st[1].y)));
		return 0;
	}
	/*for(i=1;i<=top;i++)
	{
		printf("%lld %lld\n",st[i].x,st[i].y);
	}*/
	for(i=1;i<top;i++)
	{
		double temp=cross(st[i+1],st[i]);
		double temp2=sqrt((st[i].x-temp)*(st[i].x-temp)+st[i].y*st[i].y);
		double temp3=sqrt((st[i+1].x-temp)*(st[i+1].x-temp)+st[i+1].y*st[i+1].y);
		ans=max(ans,temp2);
		//printf("%lf %lf %lf\n",temp,temp2,temp3);
	}
	double mi=1e12;
	for(i=1;i<=n;i++)
	{
		mi=min(mi,sqrt(st[i].x*st[i].x+st[i].y*st[i].x));
	}
	ans=max(ans,mi);
	
	mi=1e12;
	for(i=1;i<=n;i++)
	{
		mi=min(mi,sqrt((st[i].x-l)*(st[i].x-l)+st[i].y*st[i].x));
	}
	ans=max(ans,mi);
	printf("%lf",ans);
}

Compilation message

mobile.cpp: In function 'int main()':
mobile.cpp:76:10: warning: unused variable 'temp3' [-Wunused-variable]
   double temp3=sqrt((st[i+1].x-temp)*(st[i+1].x-temp)+st[i+1].y*st[i+1].y);
          ^~~~~
mobile.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&l);
  ~~~~~^~~~~~~~~~~~~~~~~~~
mobile.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&a[i].x,&a[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 1828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 1828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 42 ms 3312 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 47 ms 3312 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 30 ms 3312 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 3312 KB Output isn't correct
2 Halted 0 ms 0 KB -