제출 #1192651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192651		boclobanchat	Portal (BOI24_portal)	C++20	100 / 100	15 ms	3516 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ii pair<__int128,__int128>
#define fi first
#define se second
const int MAXN=1e5+5;
ii P[MAXN];
void update(ii& a,ii& b)
{
	if(a.fi<b.fi) swap(a,b);
	if(!b.fi) 
	{
		swap(a,b);
		return ;
	}
	while(a.fi)
	{
		if(a.fi<b.fi) swap(a,b);
		__int128 k=a.fi/b.fi;
		a.fi-=k*b.fi,a.se-=k*b.se;
	}
}
__int128 f(int i,int j) { return P[i].fi*P[j].se-P[i].se*P[j].fi; }
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,ans=0;
    cin>>n;
    if(n<=2) return cout<<-1,0;
    for(int i=1;i<=n;i++) 
    {
    	long long x,y;
    	cin>>x>>y;
    	P[i].fi=x,P[i].se=y;
	}
    for(int i=1;i<n;i++)
    {
    	P[i].fi-=P[i+1].fi,P[i].se-=P[i+1].se;
    	if(P[i].fi<0) P[i].fi=-P[i].fi,P[i].se=-P[i].se;
	}
    for(int i=2;i<n;i++) update(P[i-1],P[i]);
    for(int i=2;i<n-1;i++) P[i].se=__gcd(P[i].se,P[i-1].se);
    ans=f(n-2,n-1);
    if(!ans) return cout<<-1,0;
    cout<<abs(ans);
}

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