Сегодня отправил решение по одной задаче на языке C. Выбрал компилятор GNU C11, но получил TL (1 сек) на 11 тесте. Потом отправил тот же код с компилятором GNU C и получил OK (124 мс). Решение так же заходит на GNU C++ и GNU C++11. В коде не вижу UB. В задаче особо негде TL-иться. Решение O(n), n = 300000. Единственная возможная проблема: 300000 чисел на ввод и вывод. Почему в GNU C11 ввод и вывод работают в 10 раз медленнее? Или есть другая причина?

Посылки: GNU C11, GNU C.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX_N 300000
int arr[MAX_N];

int main(int pArgc, char **pArgs) {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int n;
	scanf("%d", &n);

	int k = n;
	
	printf("1 ");
	for (int i = 0; i < n; ++i) {
		int x;
		scanf("%d", &x);
		--x;
		arr[x] = 1;
		while (k > 0 && arr[k - 1])
			--k;
		printf("%d ", i + 2 - n + k);
	}

	return 0;
}

Даны три выпуклых многоугольника. Необходимо проверить, существуют ли точки, лежащие одновременно внутри всех трех данных выпуклых многоугольников. Как можно решить эту задачу за линию? Для двух выпуклых многоугольников — понятно(сумма Минковского), но как для трех?

Привет всем! Есть такая задача: Необходимо найти сумму Минковского для двух почти выпуклых многоугольников, где почти выпуклый многоугольник — многоугольник, полученный из выпуклого многоугольника путем замены некоторых ребер дугами с углом от 0 до PI радиан. (Сумма Минковского для двух многоугольников (a), (b) равна многоугольнику, полученному путем прибавления каждой точки многоугольника (a) к каждой точке многоугольника b.)

В идеале асимптотика O(n + m), где n — количество вершин первого почти выпуклого многоугольника, m — количество вершин второго почти выпуклого многоугольника.

Для просто выпуклых многоугольников сумма Минковского тривиальна, но задача с заменой некоторых ребер дугами меня ставит в тупик. Прошу помочь советом/идеей/какой-либо литературой/решением. Заранее благодарен!