QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369111#2434. Single Cut of FailureInfinityNS#WA 1061ms319640kbC++143.8kb2024-03-27 20:43:032024-03-27 20:43:05

Judging History

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

  • [2024-03-27 20:43:05]
  • 评测
  • 测评结果:WA
  • 用时:1061ms
  • 内存:319640kb
  • [2024-03-27 20:43:03]
  • 提交

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[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: 3860kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 0
Accepted
time: 167ms
memory: 70808kb

Test #10:

score: 0
Accepted
time: 162ms
memory: 71436kb

Test #11:

score: 0
Accepted
time: 195ms
memory: 84372kb

Test #12:

score: 0
Accepted
time: 161ms
memory: 65392kb

Test #13:

score: 0
Accepted
time: 182ms
memory: 70504kb

Test #14:

score: 0
Accepted
time: 228ms
memory: 84224kb

Test #15:

score: 0
Accepted
time: 177ms
memory: 66100kb

Test #16:

score: 0
Accepted
time: 193ms
memory: 84152kb

Test #17:

score: 0
Accepted
time: 213ms
memory: 83376kb

Test #18:

score: 0
Accepted
time: 162ms
memory: 71252kb

Test #19:

score: 0
Accepted
time: 208ms
memory: 84184kb

Test #20:

score: 0
Accepted
time: 163ms
memory: 83228kb

Test #21:

score: 0
Accepted
time: 215ms
memory: 83248kb

Test #22:

score: 0
Accepted
time: 155ms
memory: 70804kb

Test #23:

score: 0
Accepted
time: 196ms
memory: 83288kb

Test #24:

score: 0
Accepted
time: 918ms
memory: 318624kb

Test #25:

score: 0
Accepted
time: 1008ms
memory: 318372kb

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

score: 0
Accepted
time: 19ms
memory: 11696kb

Test #31:

score: 0
Accepted
time: 885ms
memory: 280292kb

Test #32:

score: 0
Accepted
time: 1012ms
memory: 319640kb

Test #33:

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

Test #34:

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

Test #35:

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

Test #36:

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

Test #37:

score: 0
Accepted
time: 20ms
memory: 11640kb

Test #38:

score: 0
Accepted
time: 143ms
memory: 65576kb

Test #39:

score: 0
Accepted
time: 951ms
memory: 319236kb

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

score: 0
Accepted
time: 6ms
memory: 5740kb

Test #44:

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

Test #45:

score: 0
Accepted
time: 700ms
memory: 221380kb

Test #46:

score: 0
Accepted
time: 1061ms
memory: 318108kb

Test #47:

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

Test #48:

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

Test #49:

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

Test #50:

score: -100
Wrong Answer
time: 0ms
memory: 3844kb