QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#568553#2434. Single Cut of FailureShunpowerAC ✓3800ms144588kbC++145.1kb2024-09-16 17:03:092024-09-16 17:03:10

Judging History

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

  • [2024-09-16 17:03:10]
  • 评测
  • 测评结果:AC
  • 用时:3800ms
  • 内存:144588kb
  • [2024-09-16 17:03:09]
  • 提交

answer

//Author:Leftist / Shunpower
//Rain Temperature & Cloud Moon
//May the force be with you and me.
#include <bits/stdc++.h>
#define ET return 0
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ll long long
#define ull unsigned long long
#define inf INT_MAX
#define uinf INT_MIN
#define pii pair<int,int>
#define pll pair<ll,ll>
#define debug puts("--------Chery AK IOI--------");
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define pt puts("")
#define fr1(i,a,b) for(int i=a;i<=b;i++)
#define fr2(i,a,b) for(int i=a;i>=b;i--)
#define fv(i,p) for(int i=0;i<p.size();i++)
#define ld double
#define il inline
#define ptc putchar
#define pdd pair<ld,ld>
//Quickly power: ll d=qpow(b,p>>1,k);
//Segment Tree: Memory Limit Excceed
//Segment Tree: Modify()->Pushdown()
//Mod: +M, %M, define int ll
//Mod: Don't use 998244353 instead of 1e9+7 and so on
//Don't solve a problem for too long time.
using namespace std;
const int N=1e6+10;
namespace Shun{
    int lowbit(int x){
        return x&-x;
    }
    template <typename T>
    inline void read(T &x){
       T s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){
            if(ch=='-'){
                w=-1;
            }
            ch=getchar();
        }
       while(ch>='0'&&ch<='9'){
            s=s*10+ch-'0';
            ch=getchar();
       }
       x=s*w;
    }
    template <typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>9){
            write(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace Shun;
/*
你考虑到首先有两个东西
直接连接对角线肯定可以完成整个事情
然后我们考虑怎么判断能被一条线交完
感觉只要两条线中的一条enough了?
*/
ld eps=1e-3;
int n;
ld w,h;
struct seg{
    pii x,y;
    int l,r;
    int id;
} p[N];
il int checkp(pii pos){
    if(pos.se==h) return 1;
    if(pos.fi==w) return 2;
    if(pos.se==0) return 3;
    if(pos.fi==0) return 4;
    return 0;
}
il int coff(pii pos){
    int st=checkp(pos);
    if(st==1) return pos.fi;
    if(st==2) return w+(h-pos.se);
    if(st==3) return w+h+(w-pos.fi);
    if(st==4) return w+h+w+pos.se;
    return 0;
}
map <int,int> lsh;
int bac[N<<1];
int d[N<<1];
int bol[N];
int c2,c1;
il void add(int p){
    if(!bol[p]) bol[p]++,c1++;
    else if(bol[p]==1) bol[p]++,c2++;
}
il void des(int p){
    if(bol[p]==2) bol[p]--,c2--;
    else if(bol[p]==1) bol[p]--,c1--;
}
pdd tfbac(ld x){
    pdd ans;
    // cout<<x<<endl;
    if(x<=w) ans=mp(x-0.001,h);
    else if(x<=w+h) ans=mp(w,h-(x-w)+0.001);
    else if(x<=w+h+w) ans=mp(w-(x-h-w)+0.001,0);
    else ans=mp(0,x-w-h-w-0.001);
    return ans;
}
il bool sameside(int x,int y){
    if(x>y) swap(x,y);
    if(y<=w) return 1;
    else{
        if(x<=w) return 0;
        else{
            if(y<=h+w) return 1;
            else{
                if(x<=h+w) return 0;
                else{
                    if(y<=h+w+w) return 1;
                    else{
                        if(x<=h+w+w) return 0;
                        else return 1;
                    }
                }
            }
        }
    }
}
int main(){
#ifdef SHUN
    freopen("hack.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    read(n),read(w),read(h);
    fr1(i,1,n) read(p[i].x.fi),read(p[i].x.se),read(p[i].y.fi),read(p[i].y.se),p[i].id=i;
    fr1(i,1,n){
        p[i].l=coff(p[i].x);
        p[i].r=coff(p[i].y);
        if(p[i].l>p[i].r) swap(p[i].l,p[i].r);
        lsh[p[i].l]=1,lsh[p[i].r]=1;
    }
    int tot=0;
    for(auto &i:lsh){
        tot++;
        i.se=tot;
    }
    for(auto i:lsh) bac[i.se]=i.fi;
    fr1(i,1,n){
        d[lsh[p[i].l]]=i;
        d[lsh[p[i].r]]=i;
    }
    int r=0;
    // add(d[1]);
    cout.setf(ios::fixed);
    fr1(l,1,tot){
        if(r<l) r=l-1;
        while(r<tot&&c1!=n){
            r++;
            add(d[r]);
            if(c1==n) break;
        }
        // cout<<l<<" "<<r<<" "<<c1<<" "<<c2<<endl;
        if(c1==n&&!c2){
            // if(l==r){
            //     assert(r!=n);
            //     if(!sameside(l,r+1)){
            //         cout<<"1\n";
            //         pdd p1=tfbac(bac[l],0),p2=tfbac(bac[r+1],0);
            //         cout<<setprecision(6)<<p1.fi<<" "<<p1.se<<" "<<p2.fi<<" "<<p2.se<<'\n';    
            //     }
            // }
            // else{
            // cout<<bac[l]<<" "<<bac[r+1]<<endl;
            if(!sameside(bac[l],bac[r+1])){
                // cout<<l<<" "<<r<<endl;
                cout<<"1\n";
                pdd p1=tfbac(bac[l]),p2=tfbac(bac[r+1]);
                cout<<setprecision(4)<<p1.fi<<" "<<p1.se<<" "<<p2.fi<<" "<<p2.se<<'\n';
                return 0;    
            } 
            // }
            // cout<<tfbac(bac[l])<<" "
        }
        des(d[l]);
    }
    cout<<2<<'\n';
    cout<<setprecision(4)<<0.0001<<" "<<0<<" "<<(w-0.0001)<<" "<<h<<'\n'<<0<<" "<<(h-0.0001)<<" "<<(w-0.0001)<<" "<<0<<'\n';
    ET;
}
//ETERNAL LOVE FOR LY and SHUN.

Details

Test #1:

score: 100
Accepted
time: 0ms
memory: 35588kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

score: 0
Accepted
time: 7ms
memory: 36388kb

Test #9:

score: 0
Accepted
time: 468ms
memory: 64392kb

Test #10:

score: 0
Accepted
time: 490ms
memory: 65772kb

Test #11:

score: 0
Accepted
time: 498ms
memory: 65332kb

Test #12:

score: 0
Accepted
time: 470ms
memory: 64840kb

Test #13:

score: 0
Accepted
time: 493ms
memory: 65072kb

Test #14:

score: 0
Accepted
time: 584ms
memory: 64132kb

Test #15:

score: 0
Accepted
time: 423ms
memory: 64032kb

Test #16:

score: 0
Accepted
time: 438ms
memory: 65060kb

Test #17:

score: 0
Accepted
time: 522ms
memory: 63920kb

Test #18:

score: 0
Accepted
time: 495ms
memory: 63940kb

Test #19:

score: 0
Accepted
time: 522ms
memory: 63756kb

Test #20:

score: 0
Accepted
time: 445ms
memory: 64312kb

Test #21:

score: 0
Accepted
time: 555ms
memory: 65272kb

Test #22:

score: 0
Accepted
time: 495ms
memory: 65656kb

Test #23:

score: 0
Accepted
time: 469ms
memory: 64564kb

Test #24:

score: 0
Accepted
time: 3800ms
memory: 144352kb

Test #25:

score: 0
Accepted
time: 3719ms
memory: 144536kb

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

score: 0
Accepted
time: 28ms
memory: 35736kb

Test #31:

score: 0
Accepted
time: 3125ms
memory: 129528kb

Test #32:

score: 0
Accepted
time: 3606ms
memory: 144504kb

Test #33:

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

Test #34:

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

Test #35:

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

Test #36:

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

Test #37:

score: 0
Accepted
time: 25ms
memory: 38732kb

Test #38:

score: 0
Accepted
time: 391ms
memory: 58680kb

Test #39:

score: 0
Accepted
time: 3636ms
memory: 144588kb

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

score: 0
Accepted
time: 7ms
memory: 36692kb

Test #44:

score: 0
Accepted
time: 103ms
memory: 43136kb

Test #45:

score: 0
Accepted
time: 2084ms
memory: 113484kb

Test #46:

score: 0
Accepted
time: 3763ms
memory: 144492kb

Test #47:

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

Test #48:

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

Test #49:

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

Test #50:

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

Test #51:

score: 0
Accepted
time: 7ms
memory: 35540kb

Test #52:

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

Test #53:

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

Test #54:

score: 0
Accepted
time: 7ms
memory: 36772kb

Test #55:

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

Test #56:

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

Test #57:

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

Test #58:

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

Test #59:

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

Test #60:

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

Test #61:

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

Test #62:

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

Test #63:

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

Test #64:

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

Test #65:

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

Test #66:

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

Test #67:

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

Test #68:

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

Test #69:

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

Test #70:

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

Test #71:

score: 0
Accepted
time: 56ms
memory: 45352kb

Test #72:

score: 0
Accepted
time: 62ms
memory: 45220kb

Test #73:

score: 0
Accepted
time: 76ms
memory: 45608kb

Test #74:

score: 0
Accepted
time: 69ms
memory: 45596kb

Test #75:

score: 0
Accepted
time: 51ms
memory: 45260kb

Test #76:

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