oj.uz

Submission #232811

# Submission time Handle Problem Language Result Execution time Memory
232811 2020-05-18T08:59:25 Z pedy4000 Svjetlost (COI18_svjetlost) C++14
14 / 100
 121 ms 17400 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> point;
#define X first
#define Y second

point operator- (point a, point b) {

	return point(a.X - b.X, a.Y - b.Y);
}
ll operator* (point a, point b) {

	return a.X * b.Y - a.Y * b.X;
}
bool intersect (point a, point b, point c, point d) {
	point v = b - a, u = c - d;
	if (u * v == 0)
		return false;

	if (0 < (u * v))
		return (u * v) <= ((a - d) * v);
	return (u * v) >= ((a - d) * v);
}
ld distance (point a, point b) {

	return sqrt((a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y));
}

const int N = 1e5 + 5;
int n;
point p[N];
ld res[N << 2];
ld lazy[N << 2];
int lst[N << 2];
ld len[N << 2];
set <int> live;


int dist (int a, int b) {

	return a < b? b - a: n - a + b;
}

int nxt (int a) {

	return (a + 1) % n;
}

ld getLen (int l, int r, int s = 0, int e = n, int id = 1) {
	if (l <= s && e <= r)
		return len[id];
	if (r <= s || e <= l)
		return 0;
	int mid = e + s >> 1;
	return getLen(l, r, s, mid, id << 1) + getLen(l, r, mid, e, id << 1 | 1);
}

ld calcLen (int l, int r) {
	if (l <= r)
		return getLen(l, r + 1);
	return getLen(l, n) + getLen(0, r + 1);
}

int calc (int d) {
	int s = nxt(d), e = d;
	while (dist(s, e) > 1) {
		int mid = (s + dist(s, e) / 2) % n;
		if (intersect(p[d], p[nxt(d)], p[mid], p[nxt(mid)]))
			s = mid;
		else
			e = mid;
	}
	return s;
}

void buildLen (int s = 0, int e = n, int id = 1) {
	if (e - s == 1) {
		len[id] = distance(p[s], p[nxt(s)]);
		return ;
	}

	int mid = e + s >> 1;
	buildLen(s, mid, id << 1);
	buildLen(mid, e, id << 1 | 1);
	len[id] = len[id << 1] + len[id << 1 | 1];
}

void buildResLst (int s = 0, int e = n, int id = 1) {
	if (e - s == 1) {
		lst[id] = calc(s);
		res[id] = calcLen(s, lst[id]);
		return ;
	}

	int mid = e + s >> 1;
	buildResLst(s, mid, id << 1);
	buildResLst(mid, e, id << 1 | 1);
	res[id] = max(res[id << 1], res[id << 1 | 1]);
}

void preProcess() {
	for (int i = 0; i < n; i++)
		live.insert(i);
	for (int i = 0; i < (N << 2); i++)
		lst[i] = -1;
	buildLen();
	buildResLst();
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> p[i].X >> p[i].Y;

	preProcess();
	cout << fixed << setprecision(6) << res[1] << "\n";
	return 0;
}

Compilation message

svjetlost.cpp: In function 'ld getLen(int, int, int, int, int)':
svjetlost.cpp:62:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void buildLen(int, int, int)':
svjetlost.cpp:90:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~
svjetlost.cpp: In function 'void buildResLst(int, int, int)':
svjetlost.cpp:103:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = e + s >> 1;
            ~~^~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1920 KB Unexpected end of file - double expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1920 KB Unexpected end of file - double expected
2 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1920 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 7 ms 2176 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 18 ms 3968 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 30 ms 5624 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 121 ms 17400 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 115 ms 17272 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2432 KB Unexpected end of file - double expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1920 KB Unexpected end of file - double expected
2 Halted 0 ms 0 KB -