QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369084#2434. Single Cut of FailureInfinityNS#WA 1ms4080kbC++143.1kb2024-03-27 20:22:332024-03-27 20:22:33

Judging History

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

  • [2024-03-27 20:22:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4080kb
  • [2024-03-27 20:22:33]
  • 提交

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;

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<<" ";

}

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,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]={prv,cpt};
        currh^=events[i].ss;
        prv=cpt;
    }
    mapa[currh]={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()){
            reza1=mapa[fullh^val].ff;
            reza2=mapa[fullh^val].ss;
            rezb1=mapa[val].ff;
            rezb2=mapa[val].ss;
            flag=1;
            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");
        printf("%d %d %d %d\n",0,0,w,h);
        printf("%d %d %d %d\n",w,0,0,h);
    }

    return 0;
}

Details

Test #1:

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

Test #2:

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