| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 624823 |
2022-08-08T19:46:20 Z |
paulica |
Wish (LMIO19_noras) |
C++14 |
|
2 ms |
212 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef long double ld;
typedef pair<ld,ld> pdd;
#define pb push_back
#define fr first
#define sec second
#define mp make_pair
ll n,r,m,inf=99999999999;
vector<pii> swp;
pair<int,pdd> crosspoints(ll xf, ll yf, ll xs, ll ys){
ld k=(double)(yf-ys)/(xf-xs);
//cout<<k<<endl;
ld a=yf-k*xf;
ld D=4*a*a*k*k-4*(a*a-r*r)*(1+k*k);
//cout<<D<<endl;
pair<int,pdd> ret;
if(D<0){ ret.fr=0;} //nema
else if(D==0){ ret.fr=1; //samo jed
ld x1=(-2*a*k)/(2*(1+k*k));
ret.sec.fr=x1;
//cout<<x1<<endl;
}
else{ret.fr=2; //ima
ld x1=(-2*a*k-sqrt(D))/(2*(1+k*k));
ld x2=(-2*a*k+sqrt(D))/(2*(1+k*k));
ret.sec.fr=x1; ret.sec.sec=x2;
//cout<<x1<<" "<<x2<<endl;
}
return ret;
}
bool inkruz(ll x, ld y){
if(x<-r || x>r || y<-r || y>r) return false;
ld ky=sqrt(r*r-x*x);
if(abs(ky-y)<=0.000000001){return true;}
if(ky<=0 && y<ky){return false;}
if(ky>=0 && y>ky){return false;}
return true;
}
int main(){
cin >> n >> r;
for(int i=0;i<n;i++){
ll xf,yf,xs,ys; cin >> xf>>yf>>xs>>ys;
//poseban slucaj -> xf==xs
if(xf==xs){swap(xf,yf); swap(xs,ys);}
//
pair<int,pdd> cp=crosspoints(xf,yf,xs,ys);
int lef=0; if(xf>xs){lef=1;}
ll pomx=abs(xs-xf);
if(cp.fr==0){continue;}
if(cp.fr==1){
ld x1=cp.sec.fr;
if(ceil(x1)!=floor(x1)){continue;}
if(lef && xf<x1){continue;}
if(!lef && xf>x1){continue;}
ll dif=abs(x1-xf);
if(dif%pomx!=0){continue;}
ll num=dif/pomx;
//cout<<"moz "<<num<<" do "<<num<<endl;
swp.pb(mp(num,0)); swp.pb(mp(num,1));
}
if(cp.fr==2){
ld xx1=cp.sec.fr,xx2=cp.sec.sec;
ll x1=ceil(xx1),x2=floor(xx2);
ld k=(double)(yf-ys)/(xf-xs);
ld y1=k*x1+yf-k*xf,y2=k*x2+yf-k*xf;
if(!inkruz(x1,y1) || !inkruz(x2,y2)){continue;}
//sig unutar kruga
//x1
if(lef && xf<x1){continue;}
if(!lef && xf>x1){continue;}
ll dif=abs(x1-xf);
ll num1=dif/pomx;
if(num1*pomx!=dif){num1++;
//provjera jel jos u kruznici
ll nx=xf+num1*pomx;
ld ny=k*nx+yf-k*xf;
if(!inkruz(nx,ny)){continue;}
}
//x2
if(lef && xf<x2){continue;}
if(!lef && xf>x2){continue;}
dif=abs(x2-xf);
ll num2=dif/pomx;
if(num2<num1){swap(num1,num2);}
//cout<<"moz "<<num1<<" do "<<num2<<endl;
swp.pb(mp(num1,0)); swp.pb(mp(num2,1));
}
}
sort(swp.begin(),swp.end());
ll mx=0,op=0;
for(int i=0;i<(int)swp.size();i++){
if(swp[i].sec){op--;}
else{op++;}
mx=max(mx,op);
}
cout<<mx;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
