QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#369084 | #2434. Single Cut of Failure | InfinityNS# | WA | 1ms | 4080kb | C++14 | 3.1kb | 2024-03-27 20:22:33 | 2024-03-27 20:22:33 |
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;
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<<" ";
}
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,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]={prv,cpt};
currh^=events[i].ss;
prv=cpt;
}
mapa[currh]={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()){
reza1=mapa[fullh^val].ff;
reza2=mapa[fullh^val].ss;
rezb1=mapa[val].ff;
rezb2=mapa[val].ss;
flag=1;
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");
printf("%d %d %d %d\n",0,0,w,h);
printf("%d %d %d %d\n",w,0,0,h);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4080kb
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 4072kb