Submission #1013620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013620		rainboy	Portal (BOI24_portal)	C11	100 / 100	18 ms	604 KiB

Main

#include <stdio.h>

long long abs_(long long a) { return a > 0 ? a : -a; }

typedef __int128_t L;

long long gcd(long long a, long long b) {
	return b == 0 ? a : gcd(b, a % b);
}

L cross(L x1, L y1, L x2, L y2) {
	return x1 * y2 - x2 * y1;
}

L dot(L x1, L y1, L x2, L y2) {
	return x1 * x2 + y1 * y2;
}

int main() {
	int n, x, y, x_, y_, x1, y1, x2, y2, x3, y3;
	long long d1, d1_, d2, c2, d3, c3, tmp;

	scanf("%d%d%d", &n, &x_, &y_), n--;
	x1 = y1 = 0, x2 = y2 = 0;
	while (n--) {
		scanf("%d%d", &x, &y);
		x3 = x - x_, y3 = y - y_;
		if (x3 == 0 && y3 == 0)
			continue;
		if (x1 == 0 && y1 == 0) {
			x1 = x3, y1 = y3;
			continue;
		}
		d1 = dot(x1, y1, x1, y1);
		d2 = dot(x1, y1, x2, y2), c2 = cross(x1, y1, x2, y2);
		d3 = dot(x1, y1, x3, y3), c3 = cross(x1, y1, x3, y3);
		if (c3 < 0)
			d3 = -d3, c3 = -c3;
		d3 = (d3 % d1 + d1) % d1;
		while (1) {
			if (c2 < c3)
				tmp = d2, d2 = d3, d3 = tmp, tmp = c2, c2 = c3, c3 = tmp;
			if (c3 == 0) {
				x2 = cross(x1, y1, c2, d2) / d1, y2 = dot(x1, y1, c2, d2) / d1;
				break;
			}
			d2 = ((d2 - (L) d3 * (c2 / c3)) % d1 + d1) % d1, c2 %= c3;
		}
		d1_ = gcd(d1, d3);
		x1 /= d1 / d1_, y1 /= d1 / d1_;
	}
	printf("%lld\n", x2 == 0 && y2 == 0 ? -1 : abs_(cross(x1, y1, x2, y2)));
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:23:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d%d%d", &n, &x_, &y_), n--;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:26:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d%d", &x, &y);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 29 / 29
• Subtask 5: 15 / 15
• Subtask 6: 35 / 35