QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#270959 | #5155. Faster Than Light | ucup-team173# | WA | 0ms | 43336kb | C++20 | 3.2kb | 2023-12-01 18:57:13 | 2023-12-01 18:57:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define mpr make_pair
#define pb push_back
#define fi first
#define se second
#define db double
#define y1 askdjfa
#define y2 asdkjhfa
#define x1 klsadjfa
#define x2 lkdjfa
const int maxn=211111;
const db eps=1e-15;
int x1[maxn],y1[maxn],x2[maxn],y2[maxn];
int n;
struct vec{
db x,y;
vec(db _x=0,db _y=0){
x=_x,y=_y;
}
friend vec operator +(const vec&a,const vec&b){
return vec(a.x+b.x,a.y+b.y);
}
friend vec operator -(const vec&a,const vec&b){
return vec(a.x-b.x,a.y-b.y);
}
friend db operator *(const vec&a,const vec&b){
return a.x*b.y-a.y*b.x;
}
friend vec operator *(const vec&a,const db&b){
return vec(a.x*b,a.y*b);
}
void print(){
cout<<"("<<x<<","<<y<<")";
}
};
struct line{
vec s,t;
db a;
void geta(){
a=atan2(t.y-s.y,t.x-s.x);
}
void print(){
cout<<"[";s.print();
cout<<"to";
t.print();
cout<<"]";
}
};
line ln[maxn<<1],q[maxn<<1];
vec p[maxn<<1];
int lncnt;
int xl,yl,xr,yr;
bool left(vec p,line l){
return (l.t-l.s)*(p-l.s)>0;
}
vec pos(line a,line b){
vec x=a.s-b.s;
db t=((b.t-b.s)*x)/((a.t-a.s)*(b.t-b.s));
return a.s+(a.t-a.s)*t;
}
int check(){
for(int i=1;i<=lncnt;i++)ln[i].geta();
sort(ln+1,ln+lncnt+1,[&](line a,line b){
return a.a<b.a;
});
int h=1,t=1;
q[1]=ln[1];
// for(int i=1;i<=lncnt;i++){
// ln[i].print();cout<<"\n";
// }
for(int i=2;i<=lncnt;i++){
while(h<t&&!left(p[t-1],ln[i]))t--;
while(h<t&&!left(p[h],ln[i]))h++;
if(fabs(q[t].s*ln[i].s)<eps)q[t]=left(q[t].s,ln[i])?q[t]:ln[i];
else q[++t]=ln[i];
if(h<t)p[t-1]=pos(q[t],q[t-1]);
}
while(h<t&&!left(p[t-1],q[h]))t--;
p[t]=pos(q[t],q[h]);
if(t-h<=1)return 0;
return 1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
xl=yl=-2e9;
xr=yr=2e9;
for(int i=1;i<=n;i++){
cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
xl=max(xl,x1[i]);
xr=min(xr,x2[i]);
yl=max(yl,y1[i]);
yr=min(yr,y2[i]);
}
if(xl<=xr||yl<=yr)cout<<"possible\n",exit(0);
lncnt=0;
for(int i=1;i<=n;i++){
ln[++lncnt]=(line){vec(1,y2[i]-x1[i]+eps),vec(0,y2[i]+eps)};
ln[++lncnt]=(line){vec(0,y1[i]-eps),vec(1,y1[i]-x2[i]-eps)};
}
ln[++lncnt]=(line){vec(0,1e9),vec(0,-1e9)};
ln[++lncnt]=(line){vec(0,-1e9),vec(1e9,-1e9)};
ln[++lncnt]=(line){vec(1e9,-1e9),vec(1e9,1e9)};
ln[++lncnt]=(line){vec(1e9,1e9),vec(0,1e9)};
if(check())cout<<"possible\n",exit(0);
lncnt=0;
for(int i=1;i<=n;i++){
ln[++lncnt]=(line){vec(1,y2[i]-x2[i]+eps),vec(0,y2[i]+eps)};
ln[++lncnt]=(line){vec(0,y1[i]-eps),vec(1,y1[i]-x1[i]-eps)};
}
ln[++lncnt]=(line){vec(-1e9,1e9),vec(-1e9,-1e9)};
ln[++lncnt]=(line){vec(-1e9,-1e9),vec(0,-1e9)};
ln[++lncnt]=(line){vec(0,-1e9),vec(0,1e9)};
ln[++lncnt]=(line){vec(0,1e9),vec(-1e9,1e9)};
if(check())cout<<"possible\n",exit(0);
cout<<"impossible";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 43068kb
input:
5 1 3 3 4 2 2 4 3 4 1 5 3 5 2 7 3 6 3 8 4
output:
possible
result:
ok single line: 'possible'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 43336kb
input:
4 1 1 2 2 1 3 2 4 3 1 4 2 3 3 4 4
output:
possible
result:
wrong answer 1st lines differ - expected: 'impossible', found: 'possible'