QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#369111 | #2434. Single Cut of Failure | InfinityNS# | WA | 1061ms | 319640kb | C++14 | 3.8kb | 2024-03-27 20:43:03 | 2024-03-27 20:43:05 |
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[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;
}
详细
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