Submission #56119

#	Time	Username	Problem	Language	Result	Execution time	Memory
56119		gs14004	Mobile (BOI12_mobile)	C++17	100 / 100	486 ms	16848 KiB

mobile

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;

int n, l;
pi a[1000005];
deque<pi> stk;

double cross(pi a, pi b){
	int x1 = a.first, x2 = b.first, y1 = a.second, y2 = b.second;
	return 1.0 * (1ll * x2 * x2 + 1ll * y2 * y2 - 1ll * x1 * x1 - 1ll * y1 * y1) / (2.0 * (x2 - x1));
}

double solve(double s, double e, pi t){
	return max(hypot(s - t.first, t.second), hypot(e - t.first, t.second));
}

int main(){
	scanf("%d %d",&n,&l);
	for (int i=0; i<n; i++) {
		scanf("%d %d",&a[i].first, &a[i].second);
		a[i].second = abs(a[i].second);
	}
	sort(a, a+n);
	for (int i=0; i<n; ) {
		int e = i;
		while(e < n && a[e].first == a[i].first) e++;
		while (stk.size() >= 2 && cross(stk[stk.size()-2], stk.back()) > cross(stk.back(), a[i])) {
			stk.pop_back();
		}
		stk.push_back(a[i]);
		i = e;
	}
	double ret = 0;
	while(stk.size() >= 2 && cross(stk[0], stk[1]) < 0) stk.pop_front();
	while(stk.size() >= 2 && cross(stk[stk.size()-2], stk.back()) > l) stk.pop_back();
	ret = max(ret, solve(0, cross(stk[0], stk[1]), stk[0]));
	ret = max(ret, solve(cross(stk[stk.size()-2], stk.back()), l, stk.back()));
	for(int i=1; i+1<stk.size(); i++){
		ret = max(ret, solve(cross(stk[i-1], stk[i]), cross(stk[i], stk[i+1]), stk[i]));
	}
	printf("%lf",ret);
}

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:39:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i+1<stk.size(); i++){
               ~~~^~~~~~~~~~~
mobile.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&l);
  ~~~~~^~~~~~~~~~~~~~~
mobile.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].first, &a[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5