Submission #994798

#	Time	Username	Problem	Language	Result	Execution time	Memory
994798		PenguinsAreCute	Portal (BOI24_portal)	C++17	100 / 100	70 ms	1972 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int test(int x[], int y[], int n, int p) {
	pair<int,int> l = {100,0};
	for(int i=1;i<n;i++) {
		int g = __gcd(x[i],y[i]), c = 0;
		while((!(g%p)) && c<100) g/=p, c++;
		l=min(l,{c,i});
	}
	int g = 0;
	for(int i=1;i<n;i++) g=__gcd(g,x[i]*y[l.second]-x[l.second]*y[i]);
	int c = 0; while(!(g%p)) g/=p,c++;
	return c;
}
main() {
	int n; cin >> n;
	int x[n], y[n]; for(int i=0;i<n;i++) cin>>x[i]>>y[i];
	for(int i=1;i<n;i++) x[i]-=x[0],y[i]-=y[0];
	int g=0; for(int i=2;i<n;i++) g=__gcd(g,x[1]*y[i]-x[i]*y[1]);
	if(!g) {cout<<-1; return 0;}
	g=abs(g);
	int ans = 1;
	for(int i=2;i*i<=g;i++) if(!(g%i)) {
		int k = test(x,y,n,i);
		while(k--) ans *= i;
		while(!(g%i)) g/=i;
	}
	if(g>1 && test(x,y,n,g)) ans *= g;
	cout << ans;
}

Compilation message (stderr)

Main.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main() {
      | ^~~~

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