Submission #624823

#	Time	Username	Problem	Language	Result	Execution time	Memory
624823		paulica	Wish (LMIO19_noras)	C++14	0 / 100	2 ms	212 KiB

noras

#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;
}

 

• Subtask 1: 0 / 23
• Subtask 2: 0 / 23
• Subtask 3: 0 / 15
• Subtask 4: 0 / 32
• Subtask 5: 0 / 7