QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#369132 | #2434. Single Cut of Failure | InfinityNS# | WA | 3202ms | 380644kb | C++20 | 4.0kb | 2024-03-27 20:54:23 | 2024-03-27 20:54:23 |
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);
}
};
using int128=__int128_t;
typedef pair<pt,int128> 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;
int128 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;
}
int128 get_rin128(mt19937_64 &gen){
ll pom=gen();
ll pom2=gen();
return (int128)((int128)pom^( ((int128)pom2) <<62));
}
int main(){
///freopen("test.txt","r",stdin);
scanf("%d %d %d",&n,&w,&h);
mt19937_64 gen(10);
int128 currh=0;
int128 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]=get_rin128(gen);
hval[i][1]=get_rin128(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
map<int128,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++){
int128 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: 0ms
memory: 3924kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3920kb
Test #3:
score: 0
Accepted
time: 1ms
memory: 3860kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3952kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 3844kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 4100kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 3864kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 3856kb
Test #9:
score: 0
Accepted
time: 403ms
memory: 82472kb
Test #10:
score: 0
Accepted
time: 379ms
memory: 82064kb
Test #11:
score: 0
Accepted
time: 493ms
memory: 98016kb
Test #12:
score: 0
Accepted
time: 378ms
memory: 76436kb
Test #13:
score: 0
Accepted
time: 412ms
memory: 81896kb
Test #14:
score: 0
Accepted
time: 589ms
memory: 98288kb
Test #15:
score: 0
Accepted
time: 444ms
memory: 75524kb
Test #16:
score: 0
Accepted
time: 451ms
memory: 98724kb
Test #17:
score: 0
Accepted
time: 590ms
memory: 98140kb
Test #18:
score: 0
Accepted
time: 396ms
memory: 81944kb
Test #19:
score: 0
Accepted
time: 608ms
memory: 99068kb
Test #20:
score: 0
Accepted
time: 505ms
memory: 98056kb
Test #21:
score: 0
Accepted
time: 615ms
memory: 97952kb
Test #22:
score: 0
Accepted
time: 395ms
memory: 82396kb
Test #23:
score: 0
Accepted
time: 501ms
memory: 98528kb
Test #24:
score: 0
Accepted
time: 3042ms
memory: 380644kb
Test #25:
score: 0
Accepted
time: 3174ms
memory: 380104kb
Test #26:
score: 0
Accepted
time: 1ms
memory: 3816kb
Test #27:
score: 0
Accepted
time: 0ms
memory: 3852kb
Test #28:
score: 0
Accepted
time: 1ms
memory: 3940kb
Test #29:
score: 0
Accepted
time: 2ms
memory: 4900kb
Test #30:
score: 0
Accepted
time: 37ms
memory: 13388kb
Test #31:
score: 0
Accepted
time: 2676ms
memory: 331032kb
Test #32:
score: 0
Accepted
time: 3202ms
memory: 380224kb
Test #33:
score: 0
Accepted
time: 1ms
memory: 3868kb
Test #34:
score: 0
Accepted
time: 1ms
memory: 3920kb
Test #35:
score: 0
Accepted
time: 1ms
memory: 6060kb
Test #36:
score: 0
Accepted
time: 9ms
memory: 6592kb
Test #37:
score: 0
Accepted
time: 29ms
memory: 14740kb
Test #38:
score: 0
Accepted
time: 348ms
memory: 75284kb
Test #39:
score: 0
Accepted
time: 2841ms
memory: 379836kb
Test #40:
score: 0
Accepted
time: 1ms
memory: 3872kb
Test #41:
score: 0
Accepted
time: 1ms
memory: 3880kb
Test #42:
score: 0
Accepted
time: 1ms
memory: 4208kb
Test #43:
score: 0
Accepted
time: 6ms
memory: 6116kb
Test #44:
score: 0
Accepted
time: 132ms
memory: 33720kb
Test #45:
score: 0
Accepted
time: 1998ms
memory: 259944kb
Test #46:
score: 0
Accepted
time: 3185ms
memory: 380640kb
Test #47:
score: 0
Accepted
time: 0ms
memory: 4104kb
Test #48:
score: 0
Accepted
time: 0ms
memory: 3860kb
Test #49:
score: 0
Accepted
time: 1ms
memory: 3852kb
Test #50:
score: -100
Wrong Answer
time: 0ms
memory: 3860kb