제출 #1161842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161842		kerem	Kućice (COCI21_kucice)	C++20	110 / 110	103 ms	516 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e10
#define N 100000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;

struct Pt{
	int x,y;
	Pt(){x=y=0;}
};

const int mod=1000000007;

int fp(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=ans*x%mod;
		y>>=1;x=x*x%mod;
	}
	return ans;
}
int orient(Pt a,Pt b,Pt c){
	int d=a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
	if(d>0) return 1;
	if(d<0) return -1;
	return 0;
}
void solve(){
	int n;
	cin >> n;
	vector<Pt> Point(n,Pt());
	for(int i=0;i<n;i++)
		cin >> Point[i].x >> Point[i].y;
	int ans=n*(fp(2,n)-1)%mod;
	for(int i=0;i<n;i++){
		Pt p=Point[i];
		vector<Pt> v,v1;
		for(int j=0;j<n;j++){
			if(j==i) continue;
			if(Point[j].y>=p.y) v.pb(Point[j]);
			else v1.pb(Point[j]);
		}
		sort(all(v),[p](Pt a,Pt b){
			return orient(p,a,b)>0;
		});
		sort(all(v1),[p](Pt a,Pt b){
			return orient(p,a,b)>0;
		});
		for(int j=0;j<(int)v1.size();j++)
			v.pb(v1[j]);
		int r=1;
		for(int j=0;j<n-1;j++){
			while(orient(p,v[j],v[r])>0)
				r=(r+1)%(n-1);
			int t=r-j-1+(r>j?0:n-1);
			ans=(ans-fp(2,t))%mod;
			if(ans<0) ans+=mod;
		}
	}
	cout << ans << endl;
}     
int32_t main(){
	//~ freopen("a.txt","r",stdin);
	//~ freopen("a.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 30 / 30
• Subtask 5: 30 / 30