Submission #7270738


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

struct point { double x, y; };

point  operator+(point a,  point b) { return {a.x+b.x, a.y+b.y}; }
point  operator-(point a,  point b) { return {a.x-b.x, a.y-b.y}; }
point  operator*(double t, point b) { return {t*b.x, t*b.y}; }
point  operator/(point a, double t) { return {a.x/t, a.y/t}; }

double operator*(point a,  point b) { return a.x*b.x + a.y*b.y; } // dot product
double operator%(point a,  point b) { return a.x*b.y - a.y*b.x; } // cross product

bool operator<(point a, point b) { // lexicographical compare
	if (abs(a.x-b.x) > eps) return a.x < b.x;
	return a.y + eps < b.y;
}

ostream &operator<<(ostream &out, point a) { // for debugging
	return out << "(" << a.x << "," << a.y << ")";
}

double abs(point a) { return hypot(a.x,a.y); }
point perp(point a) { return {-a.y,a.x}; } // rotate 90 degrees counterclockwise
point normalize(point a) { return a/abs(a); }

double angle(point a, point b) { // angle between two vectors (0 to pi)
	double d = normalize(a)*normalize(b);
	return acos(max(-1.0,min(1.0,d)));
}

ll ccw(point a, point b, point c) { // returns 1|0|-1 if c is left|straight|right of ab
	double res = (b-a)%(c-a);
	return abs(res) > eps ? (res > 0 ? 1 : -1) : 0;
}

bool on_segment(point p, point a, point b) {
	return (a-p)*(b-p) < eps && ccw(a,b,p) == 0;
}
void convex_hull(vector<point> &p) {
	partial_sort(begin(p), begin(p)+1, end(p));
	sort(begin(p)+1, end(p), [&](point a, point b) {
		if (ll c = ccw(p[0],a,b)) return c == 1;
		return abs(a-p[0]) < abs(b-p[0]);
	});
	ll n = sz(p), k = 2;
	FOR(i,2,n) {
		p[k++] = p[i];
		while (k >= 3 && ccw(p[k-3],p[k-2],p[k-1]) <= 0) p[k-2] = p[k-1], k--;
	}
	p.resize(k);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n; cin >> n;

	vector<point> p = {{0,0}};
	FOR(i,0,n) {
		point a;
		cin >> a.x >> a.y;
		
		vector<point> q = p;
		for (point b: p) q.pb(a+b);
		convex_hull(q);
		p = q;
	}

	double res = 0;
	for (point a: p) res = max(res, abs(a));
	cout << fixed << setprecision(20) << res << endl;
}

Submission Info

Submission Time
Task F - Engines
User pwild
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2668 Byte
Status AC
Exec Time 3 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 7
AC × 41
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 00-sample-04.txt, 00-sample-05.txt, 00-sample-06.txt, 00-sample-07.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 00-sample-04.txt, 00-sample-05.txt, 00-sample-06.txt, 00-sample-07.txt, 01-random-very-small-01.txt, 01-random-very-small-02.txt, 01-random-very-small-03.txt, 02-random-small-01.txt, 02-random-small-02.txt, 02-random-small-03.txt, 03-random-01.txt, 03-random-02.txt, 03-random-03.txt, 04-zero-01.txt, 05-same-01.txt, 05-same-02.txt, 06-linear-01.txt, 06-linear-02.txt, 06-linear-03.txt, 07-linear-positive-01.txt, 07-linear-positive-02.txt, 07-linear-positive-03.txt, 08-90-degree-01.txt, 08-90-degree-02.txt, 09-180-degree-01.txt, 09-180-degree-02.txt, 10-sandglass-01.txt, 10-sandglass-02.txt, 11-circle-01.txt, 11-circle-02.txt, 11-circle-03.txt, 11-circle-04.txt, 11-circle-05.txt, 12-square-01.txt, 12-square-02.txt, 12-square-03.txt, 13-corner-01.txt, 13-corner-02.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 1 ms 256 KB
00-sample-02.txt AC 1 ms 256 KB
00-sample-03.txt AC 1 ms 256 KB
00-sample-04.txt AC 1 ms 256 KB
00-sample-05.txt AC 1 ms 256 KB
00-sample-06.txt AC 1 ms 256 KB
00-sample-07.txt AC 1 ms 256 KB
01-random-very-small-01.txt AC 1 ms 256 KB
01-random-very-small-02.txt AC 1 ms 256 KB
01-random-very-small-03.txt AC 1 ms 256 KB
02-random-small-01.txt AC 1 ms 256 KB
02-random-small-02.txt AC 2 ms 256 KB
02-random-small-03.txt AC 2 ms 256 KB
03-random-01.txt AC 1 ms 256 KB
03-random-02.txt AC 2 ms 256 KB
03-random-03.txt AC 3 ms 256 KB
04-zero-01.txt AC 1 ms 256 KB
05-same-01.txt AC 1 ms 256 KB
05-same-02.txt AC 1 ms 256 KB
06-linear-01.txt AC 1 ms 256 KB
06-linear-02.txt AC 1 ms 256 KB
06-linear-03.txt AC 1 ms 256 KB
07-linear-positive-01.txt AC 1 ms 256 KB
07-linear-positive-02.txt AC 1 ms 256 KB
07-linear-positive-03.txt AC 1 ms 256 KB
08-90-degree-01.txt AC 2 ms 256 KB
08-90-degree-02.txt AC 3 ms 256 KB
09-180-degree-01.txt AC 2 ms 256 KB
09-180-degree-02.txt AC 3 ms 256 KB
10-sandglass-01.txt AC 2 ms 256 KB
10-sandglass-02.txt AC 3 ms 256 KB
11-circle-01.txt AC 1 ms 256 KB
11-circle-02.txt AC 1 ms 256 KB
11-circle-03.txt AC 1 ms 256 KB
11-circle-04.txt AC 2 ms 256 KB
11-circle-05.txt AC 2 ms 256 KB
12-square-01.txt AC 2 ms 256 KB
12-square-02.txt AC 2 ms 256 KB
12-square-03.txt AC 2 ms 256 KB
13-corner-01.txt AC 1 ms 256 KB
13-corner-02.txt AC 1 ms 256 KB