Submission #366362

#	Time	Username	Problem	Language	Result	Execution time	Memory
366362		kshitij_sodani	Planine (COCI21_planine)	C++14	50 / 110	1002 ms	87556 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'


llo n,aa;
llo xx[1000001];
llo yy[1000001];
vector<pair<pair<llo,llo>,pair<llo,llo>>> ss;
vector<pair<pair<llo,llo>,pair<llo,llo>>> ss3;

queue<pair<pair<llo,llo>,pair<llo,llo>>> cur;
queue<pair<pair<llo,llo>,pair<llo,llo>>> cur2;
bool cmp(pair<pair<llo,llo>,pair<llo,llo>> bb,pair<pair<llo,llo>,pair<llo,llo>> cc){
	return bb.b.a*cc.b.b<bb.b.b*cc.b.a;
}
bool cmp2(pair<pair<llo,llo>,pair<llo,llo>> bb,pair<pair<llo,llo>,pair<llo,llo>> cc){
	return bb.a.a*cc.a.b<bb.a.b*cc.a.a;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>aa;
	for(llo i=0;i<n;i++){
		cin>>xx[i]>>yy[i];
	}
	for(llo i=2;i<n-1;i+=2){
	/*	double ac=((double)aa-yy[i]);
		ac/=((double)(yy[i+1]-yy[i]));
		ac*=((double)(xx[i+1]-xx[i]));*/
		pair<llo,llo> acc2={(xx[i+1]-xx[i])*(aa-yy[i]),(yy[i+1]-yy[i])};
		acc2.a+=xx[i]*acc2.b;
		//ac+=xx[i];

		pair<llo,llo> bcc2={(xx[i-1]-xx[i])*(aa-yy[i]),(yy[i-1]-yy[i])};
		bcc2.a+=xx[i]*bcc2.b;
		//ac+=xx[i];
	/*	double bc=((double)aa-yy[i]);
		bc/=((double)(yy[i-1]-yy[i]));
		bc*=((double)(xx[i-1]-xx[i]));*/
		//bc+=xx[i];
		//cout<<setprecision(10)<<ac<<":"<<bc<<endl;
		
		/*ac*=1000000;
		bc*=1000000;
		llo acc=round(ac);
		llo bcc=round(bc);*/
		if(n<=2000){
			for(llo j=1;j<n;j+=2){
				//if(j<i){
				if(yy[j]==yy[i]){
					continue;
				}
				pair<llo,llo> ccc2={(xx[j]-xx[i])*(aa-yy[i]),(yy[j]-yy[i])};
				ccc2.a+=xx[i]*ccc2.b;
					if(j>i){
						if(acc2.a*ccc2.b>ccc2.a*acc2.b){
							acc2=ccc2;

						}
						//acc=min(acc,ccc);
					}
					if(j<i){
						if(bcc2.a*ccc2.b<ccc2.a*bcc2.b){
							bcc2=ccc2;

						}
					//	bcc=max(bcc,ccc);
					}
				//}
			}
		}
		long double ac=((long double)(acc2.a))/((long double)(acc2.b));
		long double bc=((long double)(bcc2.a))/((long double)(bcc2.b));
		/*ac*=100000000;
		bc*=100000000;
		llo acc=round(ac);
		llo bcc=round(bc);*/
		swap(ac,bc);
		swap(acc2,bcc2);
		ss.pb({acc2,bcc2});
		ss3.pb({acc2,bcc2});
		//cout<<setprecision(5)<<ac<<":"<<bc<<endl;
			//cout<<acc<<","<<bcc<<endl;

	}
	sort(ss.begin(),ss.end(),cmp);
	sort(ss3.begin(),ss3.end(),cmp2);
	//return 0;



	for(auto j:ss){
		cur2.push(j);
		//cur.insert(j);
	//	cur2.insert({j.b,j.a});
	}
	for(auto j:ss3){
		cur.push(j);
	}
//	sort(ss.begin(),ss.end(),cmp);
	llo ans=0;
	map<pair<pair<llo,llo>,pair<llo,llo>>,llo> kk4;
	while(cur2.size()){
		
		pair<pair<llo,llo>,pair<llo,llo>> no=cur2.front();
	
		cur2.pop();
		if(kk4.find(no)!=kk4.end()){
			continue;
		}
		//cout<<no.b.a<<"::"<<no.b.b<<endl;

		ans++;
	//	cout<<no.a<<":"<<no.b<<endl;
		while(cur.size()){
			pair<pair<llo,llo>,pair<llo,llo>> no2=cur.front();
		//	cout<<no2.a<<",,"<<no2.b<<endl;
			if(no2.a.a*no.b.b<=no.b.a*no2.a.b){	
				kk4[no2]++;
				cur.pop();

			/*	cur.erase(no2);
				cur2.erase({no2.b,no2.a});*/
			}
			else{
				break;
			}
		}
		//break;
	}



	cout<<ans<<endl;




 
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60