Submission #561944

#	Time	Username	Problem	Language	Result	Execution time	Memory
561944		kingfran1907	Svjetlost (COI18_svjetlost)	C++14	0 / 100	3 ms	700 KiB

Main

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;
const double half = atan2(0, -1);

inline llint ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
	return (llint)a.X * (b.Y - c.Y) + (llint)b.X * (c.Y - a.Y) + (llint)c.X * (a.Y - b.Y);
}

double dist(pair<int, int> a, pair<int, int> b) {
	llint outx = a.X - b.X;
	llint outy = a.Y - b.Y;
	return sqrt(outx * outx + outy * outy);
}

inline double len(pair<int, int> a) {
	return dist(a, {0, 0});
}

inline double angl(pair<int, int> a) {
	return atan2(a.Y, a.X);
}

int n, q;
pair<int, int> niz[maxn];
pair<int, int> vec[maxn], cp[maxn];
double ang[maxn];
double tour[treesiz], prop[treesiz];
set< pair<double, int> > s;

void send(int x) {
	tour[x * 2] += prop[x];
	tour[x * 2 + 1] += prop[x];
	
	prop[x * 2] += prop[x];
	prop[x * 2 + 1] += prop[x];
	prop[x] = 0;
}

void update(int a, int b, int l, int r, int node, double val) {
	if (l > b || r < a) return;
	if (l >= a && r <= b) {
		tour[node] += val;
		prop[node] += val;
		return;
	}
	
	int mid = (l + r) / 2;
	update(a, b, l, mid, node * 2, val);
	update(a, b, mid + 1, r, node * 2 + 1, val);
	tour[node] = max(tour[node * 2], tour[node * 2 + 1]);
}

void update_interval(int a, int b, double val) {
	if (a <= b) update(a, b, 0, off - 1, 1, val);
	else {
		update(a, n - 1, 0, off - 1, 1, val);
		update(0, b, 0, off - 1, 1, val);
	}
}

int get_lef(double ang) {
	double tang = ang + half;
	if (tang > half) tang -= 2 * half;
	
	auto iter = s.upper_bound({tang, n + 1});
	if (iter == s.end()) iter = s.begin();
	return iter->Y;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		niz[i] = {a, b};
	}
	
	for (int i = 0; i < n; i++) {
		vec[i] = {niz[(i + 1) % n].X - niz[i].X, niz[(i + 1) % n].Y - niz[i].Y};
		ang[i] = angl(vec[i]);
		cp[i] = vec[i];
		s.insert({ang[i], i});
	}
	int cnt = 0;
	for (auto iter : s) 
		vec[cnt] = cp[iter.Y], ang[cnt] = iter.X, cnt++;
	s.clear();
	for (int i = 0; i < n; i++)
		s.insert({ang[i], i});
	
	for (int i = 0; i < n; i++) {
		int ind = get_lef(ang[i]);
		update_interval(ind, i, len(vec[i]));
	}
	printf("%.10f\n", tour[1]);
	
	scanf("%d", &q);
	while (q--) {
		int x; scanf("%d", &x); x--;
	}
	return 0;
}

Compilation message (stderr)

svjetlost.cpp: In function 'int main()':
svjetlost.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
svjetlost.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
svjetlost.cpp:108:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |   int x; scanf("%d", &x); x--;
      |          ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31