Submission #99203

#	Time	Username	Problem	Language	Result	Execution time	Memory
99203		dsg213	Relay (COI16_relay)	C++14	100 / 100	238 ms	9436 KiB

relay

#include<bits/stdc++.h>
#define mp make_pair
#define st first
#define nd second
#define ll long long
using namespace std;
struct pkt{
	ll x;
	ll y;
};
ll det(pkt a,pkt b,pkt c){
	return a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y;
}
int nalewo(pkt pds1,pkt pds2,pkt spr){
	return det(pds1,pds2,spr)>0;
}
int naprawo(pkt pds1,pkt pds2,pkt spr){
	return det(pds1,pds2,spr)<0;
}
pkt sta[110000];
pkt wys[210000];
int zaz[110000];
int n,m;
pair<int,int> odpal(int x){
	int mxl=0,mxp=0;
	for(int i=0;i<m;i++){
		if(naprawo(sta[x],wys[mxp],wys[i])){
			mxp=i;
		}
	}
	for(int i=0;i<m;i++){
		if(nalewo(sta[x],wys[mxl],wys[i])){
			mxl=i;
		}
	}
	for(int i=0;i<n;i++){
		if(!naprawo(sta[x],wys[mxl],sta[i])){
			zaz[i]=1;
		}
	}
	for(int i=0;i<n;i++){
		if(!nalewo(sta[x],wys[mxp],sta[i])){
			zaz[i]=1;
		}
	}
	for(int i=0;i<n;i++){
		if(naprawo(wys[mxl],wys[mxp],sta[i])){
			zaz[i]=1;
		}
	}
	return mp(mxl,mxp);
}
int main(){
			
	cin >>n;
	for(int i=0;i<n;i++){
		zaz[i]=0;
		cin >>sta[i].x >>sta[i].y;
	}
	cin >>m;
	for(int i=0;i<m;i++){
		cin >>wys[i].x >>wys[i].y;
	}
	for(int i=0;i<m;i++){
		wys[i+m]=wys[i];
	}
	pair<int,int> pr=odpal(0);
	int mxl=pr.st+m,mxp=pr.nd;
	int ktl=-1,ktp=-1;
	/*for(int i=0;i<n;i++){
		cout <<zaz[i] <<" ";
	}
	cout <<"\n";*/
	int z=0;
	for(int i=0;i<n;i++){
		if(!zaz[i]){
			continue;
		}
		z++;
		while(mxl !=0 && naprawo(wys[mxl-1],wys[mxl],sta[i])){
			mxl--;
			ktl=-1;
		}
		if(mxl==0){
			cout <<""<<n;
			return 0;
		}
		if(ktl==-1 || nalewo(sta[ktl],wys[mxl],sta[i])){
			ktl=i;
		}
		while(mxp !=m+m-2 && naprawo(wys[mxp],wys[mxp+1],sta[i])){
			mxp++;
			ktp=-1;
		}
		if(mxp==m+m-2){
			cout <<""<<n;
			return 0;
		}
		if(ktp==-1 || nalewo(sta[i],wys[mxp],sta[ktp])){
			ktp=i;
		}
	}
	//cout <<"\n\n"<<ktl <<" "<<ktp<<"\n";
	//cout <<sta[ktl].x <<" "<<sta[ktl].y <<"	"<<sta[ktp].x <<" "<<sta[ktp].y <<"\n";
	odpal(ktl);
	odpal(ktp);
	int wyn=0;
	for(int i=0;i<n;i++){
		if(zaz[i])wyn++;
	}
	cout <<wyn-1<<"\n";
}

• Subtask 1: 18 / 18
• Subtask 2: 19 / 19
• Subtask 3: 20 / 20
• Subtask 4: 43 / 43