QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#568553 | #2434. Single Cut of Failure | Shunpower | AC ✓ | 3800ms | 144588kb | C++14 | 5.1kb | 2024-09-16 17:03:09 | 2024-09-16 17:03:10 |
Judging History
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