QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369154#2434. Single Cut of FailureInfinityNS#WA 3305ms381148kbC++204.2kb2024-03-27 21:08:102024-03-27 21:08:10

Judging History

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

  • [2024-03-27 21:08:10]
  • 评测
  • 测评结果:WA
  • 用时:3305ms
  • 内存:381148kb
  • [2024-03-27 21:08:10]
  • 提交

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

};

using int128=__uint128_t;
typedef pair<pt,int128> 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;
int128 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;

}

int128 get_rin128(mt19937_64 &gen){
    ll pom=gen();
    ll pom2=gen();
    return (int128)((int128)pom^( ((int128)pom2) <<60));
}

void isp128(int128 x){

    while(x){
        cout<<(ll)(x%10)<<" ";
        x/=10;
    }
    cout<<endl;

}

int main(){

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

    scanf("%d %d %d",&n,&w,&h);
    mt19937_64 gen(10);
    int128 currh=0;
    int128 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]=get_rin128(gen);
        hval[i][1]=get_rin128(gen);

        ///isp128(hval[i][0]);

        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

    map<int128,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++){

        int128 val=it->ff;

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

            assert((fullh^val)!=val);

            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[i])){
                    reza1=aa[i].ff;
                    reza2=aa[i].ss;
                    rezb1=bb[i].ff;
                    rezb2=bb[i].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: 4040kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 0
Accepted
time: 386ms
memory: 81472kb

Test #10:

score: 0
Accepted
time: 382ms
memory: 81360kb

Test #11:

score: 0
Accepted
time: 520ms
memory: 96780kb

Test #12:

score: 0
Accepted
time: 369ms
memory: 77612kb

Test #13:

score: 0
Accepted
time: 406ms
memory: 83084kb

Test #14:

score: 0
Accepted
time: 602ms
memory: 97444kb

Test #15:

score: 0
Accepted
time: 427ms
memory: 76904kb

Test #16:

score: 0
Accepted
time: 472ms
memory: 97764kb

Test #17:

score: 0
Accepted
time: 602ms
memory: 97888kb

Test #18:

score: 0
Accepted
time: 416ms
memory: 82420kb

Test #19:

score: 0
Accepted
time: 602ms
memory: 98892kb

Test #20:

score: 0
Accepted
time: 474ms
memory: 98332kb

Test #21:

score: 0
Accepted
time: 618ms
memory: 98980kb

Test #22:

score: 0
Accepted
time: 400ms
memory: 82992kb

Test #23:

score: 0
Accepted
time: 480ms
memory: 98916kb

Test #24:

score: 0
Accepted
time: 2725ms
memory: 379604kb

Test #25:

score: 0
Accepted
time: 3283ms
memory: 379684kb

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

score: 0
Accepted
time: 4ms
memory: 4988kb

Test #30:

score: 0
Accepted
time: 31ms
memory: 13464kb

Test #31:

score: 0
Accepted
time: 2754ms
memory: 329640kb

Test #32:

score: 0
Accepted
time: 3305ms
memory: 380396kb

Test #33:

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

Test #34:

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

Test #35:

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

Test #36:

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

Test #37:

score: 0
Accepted
time: 26ms
memory: 13580kb

Test #38:

score: 0
Accepted
time: 355ms
memory: 74760kb

Test #39:

score: 0
Accepted
time: 3051ms
memory: 378988kb

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

score: 0
Accepted
time: 9ms
memory: 6092kb

Test #44:

score: 0
Accepted
time: 125ms
memory: 31540kb

Test #45:

score: 0
Accepted
time: 2014ms
memory: 260492kb

Test #46:

score: 0
Accepted
time: 3228ms
memory: 381148kb

Test #47:

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

Test #48:

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

Test #49:

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

Test #50:

score: -100
Wrong Answer
time: 1ms
memory: 3848kb