//#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<llo,llo>> ss;
set<pair<llo,llo>> cur;
set<pair<llo,llo>> cur2;
llo ap[1000001];
llo bp[1000001];
bool clock(pair<llo,llo> aa,pair<llo,llo> bb,pair<llo,llo> cc){
return aa.a*(bb.b-cc.b)+bb.a*(cc.b-aa.b)+cc.a*(aa.b-bb.b)<0;
}
bool clock2(pair<llo,llo> aa,pair<llo,llo> bb,pair<llo,llo> cc){
return aa.a*(bb.b-cc.b)+bb.a*(cc.b-aa.b)+cc.a*(aa.b-bb.b)<=0;
}
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];
}
vector<pair<pair<llo,llo>,llo>> sss;
for(llo i=1;i<n;i+=2){
while(sss.size()>=2){
if(!clock(sss[sss.size()-2].a,sss.back().a,{xx[i],yy[i]})){
sss.pop_back();
continue;
}
else{
break;
}
}
sss.pb({{xx[i],yy[i]},i});
llo ind=0;
/*llo low=0;
llo high=sss.size()-1;*/
/*while(low<high-1){
llo mid=(low+high)/2;
if(clock({xx[i+1],yy[i+1]},sss[ind-(1<<j)+1].a,sss[ind-(1<<j)].a)){
ind-=(1<<j);
}
}*/
for(llo j=19;j>=0;j--){
if(ind+(1<<j)<sss.size()){
if(clock2(sss[ind+(1<<j)-1].a,sss[ind+(1<<j)].a,{xx[i+1],yy[i+1]})){
ind+=(1<<j);
}
}
}
ap[i+1]=sss[ind].b;
}
//return 0;
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=ap[i];j<=ap[i];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(bcc2.a*ccc2.b<ccc2.a*bcc2.b){
bcc2=ccc2;
}
// bcc=max(bcc,ccc);
}
//}
}
for(llo j=i+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*=1000000;
bc*=1000000;
llo acc=round(ac);
llo bcc=round(bc);
swap(acc,bcc);
ss.pb({acc,bcc});
//cout<<acc<<","<<bcc<<endl;
}
//return 0;
for(auto j:ss){
cur.insert(j);
cur2.insert({j.b,j.a});
}
// sort(ss.begin(),ss.end(),cmp);
llo ans=0;
while(cur2.size()){
ans++;
pair<llo,llo> no=*(cur2.begin());
// cout<<no.a<<":"<<no.b<<endl;
while(cur.size()){
pair<llo,llo> no2=*(cur.begin());
// cout<<no2.a<<",,"<<no2.b<<endl;
if(no2.a<=no.a){
cur.erase(no2);
cur2.erase({no2.b,no2.a});
}
else{
break;
}
}
//break;
}
cout<<ans<<endl;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:58:17: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if(ind+(1<<j)<sss.size()){
| ~~~~~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
1260 KB |
Output is correct |
| 2 |
Correct |
46 ms |
1260 KB |
Output is correct |
| 3 |
Correct |
47 ms |
1260 KB |
Output is correct |
| 4 |
Execution timed out |
2096 ms |
3056 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
620 KB |
Output is correct |
| 2 |
Correct |
3 ms |
620 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
3 ms |
620 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
3 ms |
620 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
1260 KB |
Output is correct |
| 2 |
Correct |
46 ms |
1260 KB |
Output is correct |
| 3 |
Correct |
47 ms |
1260 KB |
Output is correct |
| 4 |
Execution timed out |
2096 ms |
3056 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
