QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#369178 | #2434. Single Cut of Failure | InfinityNS# | AC ✓ | 1051ms | 319616kb | C++20 | 3.8kb | 2024-03-27 21:29:27 | 2024-03-27 21:29:27 |
Judging History
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[j])){
reza1=aa[i].ff;
reza2=aa[i].ss;
rezb1=bb[j].ff;
rezb2=bb[j].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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3852kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3864kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 4072kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3844kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 3952kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 3888kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 3864kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 3864kb
Test #9:
score: 0
Accepted
time: 165ms
memory: 70748kb
Test #10:
score: 0
Accepted
time: 166ms
memory: 71392kb
Test #11:
score: 0
Accepted
time: 207ms
memory: 83940kb
Test #12:
score: 0
Accepted
time: 181ms
memory: 64680kb
Test #13:
score: 0
Accepted
time: 160ms
memory: 71588kb
Test #14:
score: 0
Accepted
time: 204ms
memory: 83184kb
Test #15:
score: 0
Accepted
time: 158ms
memory: 64968kb
Test #16:
score: 0
Accepted
time: 187ms
memory: 83260kb
Test #17:
score: 0
Accepted
time: 212ms
memory: 82896kb
Test #18:
score: 0
Accepted
time: 178ms
memory: 70352kb
Test #19:
score: 0
Accepted
time: 198ms
memory: 83164kb
Test #20:
score: 0
Accepted
time: 198ms
memory: 83848kb
Test #21:
score: 0
Accepted
time: 198ms
memory: 83768kb
Test #22:
score: 0
Accepted
time: 176ms
memory: 71484kb
Test #23:
score: 0
Accepted
time: 204ms
memory: 82532kb
Test #24:
score: 0
Accepted
time: 936ms
memory: 318760kb
Test #25:
score: 0
Accepted
time: 1015ms
memory: 318964kb
Test #26:
score: 0
Accepted
time: 1ms
memory: 3868kb
Test #27:
score: 0
Accepted
time: 0ms
memory: 3844kb
Test #28:
score: 0
Accepted
time: 1ms
memory: 3956kb
Test #29:
score: 0
Accepted
time: 3ms
memory: 4548kb
Test #30:
score: 0
Accepted
time: 14ms
memory: 11804kb
Test #31:
score: 0
Accepted
time: 856ms
memory: 281152kb
Test #32:
score: 0
Accepted
time: 1051ms
memory: 318136kb
Test #33:
score: 0
Accepted
time: 1ms
memory: 4096kb
Test #34:
score: 0
Accepted
time: 1ms
memory: 4124kb
Test #35:
score: 0
Accepted
time: 0ms
memory: 3956kb
Test #36:
score: 0
Accepted
time: 3ms
memory: 5608kb
Test #37:
score: 0
Accepted
time: 8ms
memory: 11592kb
Test #38:
score: 0
Accepted
time: 144ms
memory: 63868kb
Test #39:
score: 0
Accepted
time: 942ms
memory: 318968kb
Test #40:
score: 0
Accepted
time: 1ms
memory: 4088kb
Test #41:
score: 0
Accepted
time: 0ms
memory: 3876kb
Test #42:
score: 0
Accepted
time: 1ms
memory: 3980kb
Test #43:
score: 0
Accepted
time: 0ms
memory: 5532kb
Test #44:
score: 0
Accepted
time: 58ms
memory: 27020kb
Test #45:
score: 0
Accepted
time: 679ms
memory: 221544kb
Test #46:
score: 0
Accepted
time: 1025ms
memory: 319616kb
Test #47:
score: 0
Accepted
time: 1ms
memory: 4076kb
Test #48:
score: 0
Accepted
time: 1ms
memory: 3920kb
Test #49:
score: 0
Accepted
time: 1ms
memory: 3924kb
Test #50:
score: 0
Accepted
time: 1ms
memory: 3860kb
Test #51:
score: 0
Accepted
time: 0ms
memory: 3908kb
Test #52:
score: 0
Accepted
time: 1ms
memory: 4040kb
Test #53:
score: 0
Accepted
time: 0ms
memory: 4080kb
Test #54:
score: 0
Accepted
time: 0ms
memory: 3868kb
Test #55:
score: 0
Accepted
time: 0ms
memory: 3860kb
Test #56:
score: 0
Accepted
time: 0ms
memory: 3864kb
Test #57:
score: 0
Accepted
time: 0ms
memory: 3908kb
Test #58:
score: 0
Accepted
time: 1ms
memory: 4092kb
Test #59:
score: 0
Accepted
time: 1ms
memory: 3840kb
Test #60:
score: 0
Accepted
time: 0ms
memory: 3864kb
Test #61:
score: 0
Accepted
time: 0ms
memory: 3848kb
Test #62:
score: 0
Accepted
time: 1ms
memory: 3868kb
Test #63:
score: 0
Accepted
time: 1ms
memory: 3872kb
Test #64:
score: 0
Accepted
time: 0ms
memory: 3840kb
Test #65:
score: 0
Accepted
time: 1ms
memory: 3948kb
Test #66:
score: 0
Accepted
time: 0ms
memory: 3952kb
Test #67:
score: 0
Accepted
time: 1ms
memory: 4044kb
Test #68:
score: 0
Accepted
time: 0ms
memory: 3844kb
Test #69:
score: 0
Accepted
time: 1ms
memory: 3844kb
Test #70:
score: 0
Accepted
time: 1ms
memory: 3888kb
Test #71:
score: 0
Accepted
time: 55ms
memory: 32644kb
Test #72:
score: 0
Accepted
time: 57ms
memory: 32480kb
Test #73:
score: 0
Accepted
time: 61ms
memory: 35652kb
Test #74:
score: 0
Accepted
time: 68ms
memory: 36940kb
Test #75:
score: 0
Accepted
time: 48ms
memory: 34208kb
Test #76:
score: 0
Accepted
time: 1ms
memory: 3872kb