QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369178#2434. Single Cut of FailureInfinityNS#AC ✓1051ms319616kbC++203.8kb2024-03-27 21:29:272024-03-27 21:29:27

Judging History

你现在查看的是最新测评结果

  • [2024-03-27 21:29:27]
  • 评测
  • 测评结果:AC
  • 用时:1051ms
  • 内存:319616kb
  • [2024-03-27 21:29:27]
  • 提交

answer

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}


const int maxn=2e6+10;

struct pt{
    ll x,y;

    pt(){}
    pt(ll x,ll y){
        this->x=x;
        this->y=y;
    }

    pt operator -(pt b){
        return pt(x-b.x,y-b.y);
    }
    pt operator +(pt b){
        return pt(x+b.x,y+b.y);
    }


    ll cross(pt b){
        return x*b.y-y*b.x;
    }

    ll sqdist(){
        return x*x+y*y;
    }

    void ispis(){
        printf("%lld %lld PT\n",x,y);
    }

};

typedef pair<pt,ll> ptl;
typedef pair<pt,pt> ptt;

bool cmp(ptl &a,ptl &b){

    pt pta=a.ff;
    pt ptb=b.ff;

    ll pom=pta.cross(ptb);

    if(pom>0)return 1;
    if(pom<0)return 0;

    if(pta.x==0)return pta.y>ptb.y;
    return pta.x<ptb.x;
}

int n,w,h;
ll hval[maxn][2];

void ispisi(pt a,pt b){

    cout<<fixed<<setprecision(11)<<((double)a.x+b.x)/2<<" "<<((double)a.y+b.y)/2<<" ";

}

bool nisu_uliniji(ptt a,ptt b){

    if(a.ff.x==a.ss.x && a.ss.x==b.ff.x && b.ff.x==b.ss.x)return false;
    if(a.ff.y==a.ss.y && a.ss.y==b.ff.y && b.ff.y==b.ss.y)return false;
    return true;

}

int main(){

    ///freopen("test.txt","r",stdin);

    scanf("%d %d %d",&n,&w,&h);
    mt19937_64 gen(10);
    ll currh=0;
    ll fullh=0;
    vector<ptl>events;
    for(int i=1;i<=n;i++){
        pt a,b;
        scanf("%lld %lld %lld %lld",&a.x,&a.y,&b.x,&b.y);
        if(a.cross(b)<0)swap(a,b);
        hval[i][0]=gen();
        hval[i][1]=gen();
        currh^=hval[i][0];
        fullh^=hval[i][0];
        fullh^=hval[i][1];
        events.pb({a,hval[i][0]^hval[i][1]});
        events.pb({b,hval[i][0]^hval[i][1]});
    }

    events.pb({pt(w,0),0});
    events.pb({pt(0,h),0});
    events.pb({pt(w,h),0});

    sort(events.begin(),events.end(),cmp);

    pt prv(0,0);
    /// isto i kad zavrsis probaj sa 00

    unordered_map<ll,vector<pair<pt,pt>> >mapa;
    mapa.reserve(4*n);
    mapa.max_load_factor(0.25);
    for(int i=0;i<events.size();i++){
        pt cpt=events[i].ff;
        mapa[currh].pb({prv,cpt});
        currh^=events[i].ss;
        prv=cpt;
    }
    mapa[currh].pb({prv,pt(0,0)});

    pt reza1,reza2,rezb1,rezb2;
    bool flag=0;
    for(auto it=mapa.begin();it!=mapa.end();it++){

        ll val=it->ff;

        if(mapa.find(fullh^val)!=mapa.end()){

            vector<ptt>&aa=it->ss;
            vector<ptt>&bb=mapa[fullh^val];

            for(int i=0;i<aa.size();i++){
            for(int j=0;j<bb.size();j++){
                if(nisu_uliniji(aa[i],bb[j])){
                    reza1=aa[i].ff;
                    reza2=aa[i].ss;
                    rezb1=bb[j].ff;
                    rezb2=bb[j].ss;
                    flag=1;
                    break;
                }
            }
            if(flag)break;
            }

            if(flag)break;
        }

    }

    if(flag){
        printf("1\n");

        /*reza1.ispis();
        reza2.ispis();
        rezb1.ispis();
        rezb2.ispis();*/

        ispisi(reza1,reza2);
        ispisi(rezb1,rezb2);
        printf("\n");
    }
    else{

        printf("2\n");
        cout<<fixed<<setprecision(11)<<0<<" "<<0.5<<" "<<(double)w-0.5<<" "<<h<<endl;
        cout<<fixed<<setprecision(11)<<w<<" "<<0.5<<" "<<0.5<<" "<<h<<endl;
    }

    return 0;
}

Details

Test #1:

score: 100
Accepted
time: 1ms
memory: 3852kb

Test #2:

score: 0
Accepted
time: 1ms
memory: 3864kb

Test #3:

score: 0
Accepted
time: 0ms
memory: 4072kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 3844kb

Test #5:

score: 0
Accepted
time: 1ms
memory: 3952kb

Test #6:

score: 0
Accepted
time: 1ms
memory: 3888kb

Test #7:

score: 0
Accepted
time: 0ms
memory: 3864kb

Test #8:

score: 0
Accepted
time: 0ms
memory: 3864kb

Test #9:

score: 0
Accepted
time: 165ms
memory: 70748kb

Test #10:

score: 0
Accepted
time: 166ms
memory: 71392kb

Test #11:

score: 0
Accepted
time: 207ms
memory: 83940kb

Test #12:

score: 0
Accepted
time: 181ms
memory: 64680kb

Test #13:

score: 0
Accepted
time: 160ms
memory: 71588kb

Test #14:

score: 0
Accepted
time: 204ms
memory: 83184kb

Test #15:

score: 0
Accepted
time: 158ms
memory: 64968kb

Test #16:

score: 0
Accepted
time: 187ms
memory: 83260kb

Test #17:

score: 0
Accepted
time: 212ms
memory: 82896kb

Test #18:

score: 0
Accepted
time: 178ms
memory: 70352kb

Test #19:

score: 0
Accepted
time: 198ms
memory: 83164kb

Test #20:

score: 0
Accepted
time: 198ms
memory: 83848kb

Test #21:

score: 0
Accepted
time: 198ms
memory: 83768kb

Test #22:

score: 0
Accepted
time: 176ms
memory: 71484kb

Test #23:

score: 0
Accepted
time: 204ms
memory: 82532kb

Test #24:

score: 0
Accepted
time: 936ms
memory: 318760kb

Test #25:

score: 0
Accepted
time: 1015ms
memory: 318964kb

Test #26:

score: 0
Accepted
time: 1ms
memory: 3868kb

Test #27:

score: 0
Accepted
time: 0ms
memory: 3844kb

Test #28:

score: 0
Accepted
time: 1ms
memory: 3956kb

Test #29:

score: 0
Accepted
time: 3ms
memory: 4548kb

Test #30:

score: 0
Accepted
time: 14ms
memory: 11804kb

Test #31:

score: 0
Accepted
time: 856ms
memory: 281152kb

Test #32:

score: 0
Accepted
time: 1051ms
memory: 318136kb

Test #33:

score: 0
Accepted
time: 1ms
memory: 4096kb

Test #34:

score: 0
Accepted
time: 1ms
memory: 4124kb

Test #35:

score: 0
Accepted
time: 0ms
memory: 3956kb

Test #36:

score: 0
Accepted
time: 3ms
memory: 5608kb

Test #37:

score: 0
Accepted
time: 8ms
memory: 11592kb

Test #38:

score: 0
Accepted
time: 144ms
memory: 63868kb

Test #39:

score: 0
Accepted
time: 942ms
memory: 318968kb

Test #40:

score: 0
Accepted
time: 1ms
memory: 4088kb

Test #41:

score: 0
Accepted
time: 0ms
memory: 3876kb

Test #42:

score: 0
Accepted
time: 1ms
memory: 3980kb

Test #43:

score: 0
Accepted
time: 0ms
memory: 5532kb

Test #44:

score: 0
Accepted
time: 58ms
memory: 27020kb

Test #45:

score: 0
Accepted
time: 679ms
memory: 221544kb

Test #46:

score: 0
Accepted
time: 1025ms
memory: 319616kb

Test #47:

score: 0
Accepted
time: 1ms
memory: 4076kb

Test #48:

score: 0
Accepted
time: 1ms
memory: 3920kb

Test #49:

score: 0
Accepted
time: 1ms
memory: 3924kb

Test #50:

score: 0
Accepted
time: 1ms
memory: 3860kb

Test #51:

score: 0
Accepted
time: 0ms
memory: 3908kb

Test #52:

score: 0
Accepted
time: 1ms
memory: 4040kb

Test #53:

score: 0
Accepted
time: 0ms
memory: 4080kb

Test #54:

score: 0
Accepted
time: 0ms
memory: 3868kb

Test #55:

score: 0
Accepted
time: 0ms
memory: 3860kb

Test #56:

score: 0
Accepted
time: 0ms
memory: 3864kb

Test #57:

score: 0
Accepted
time: 0ms
memory: 3908kb

Test #58:

score: 0
Accepted
time: 1ms
memory: 4092kb

Test #59:

score: 0
Accepted
time: 1ms
memory: 3840kb

Test #60:

score: 0
Accepted
time: 0ms
memory: 3864kb

Test #61:

score: 0
Accepted
time: 0ms
memory: 3848kb

Test #62:

score: 0
Accepted
time: 1ms
memory: 3868kb

Test #63:

score: 0
Accepted
time: 1ms
memory: 3872kb

Test #64:

score: 0
Accepted
time: 0ms
memory: 3840kb

Test #65:

score: 0
Accepted
time: 1ms
memory: 3948kb

Test #66:

score: 0
Accepted
time: 0ms
memory: 3952kb

Test #67:

score: 0
Accepted
time: 1ms
memory: 4044kb

Test #68:

score: 0
Accepted
time: 0ms
memory: 3844kb

Test #69:

score: 0
Accepted
time: 1ms
memory: 3844kb

Test #70:

score: 0
Accepted
time: 1ms
memory: 3888kb

Test #71:

score: 0
Accepted
time: 55ms
memory: 32644kb

Test #72:

score: 0
Accepted
time: 57ms
memory: 32480kb

Test #73:

score: 0
Accepted
time: 61ms
memory: 35652kb

Test #74:

score: 0
Accepted
time: 68ms
memory: 36940kb

Test #75:

score: 0
Accepted
time: 48ms
memory: 34208kb

Test #76:

score: 0
Accepted
time: 1ms
memory: 3872kb