QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#209986 | #5155. Faster Than Light | ucup-team1004 | WA | 1ms | 9864kb | C++14 | 3.0kb | 2023-10-10 21:08:53 | 2023-10-10 21:08:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=2e5+10,INF=1e9+1;
int n;
struct zj{
int l,r,x,y;
}a[N];
struct vec{
int x,y;
vec(int a=0,int b=0):x(a),y(b){}
};
ostream& operator << (ostream &out,const vec &x){
return out<<'('<<x.x<<','<<x.y<<')';
}
vec operator - (const vec &a,const vec &b){
return vec(a.x-b.x,a.y-b.y);
}
vec operator * (const vec &a,const int &k){
return vec(a.x*k,a.y*k);
}
ll cross(const vec &a,const vec &b){
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
ll dot(const vec &a,const vec &b){
return 1ll*a.x*b.x+1ll*a.y*b.y;
}
ll dis2(const vec &a){
return dot(a,a);
}
void ok(){
puts("possible"),exit(0);
}
void chk1(){
int L=0,R=INF;
for(int i=1;i<=n;i++){
L=max(L,a[i].l),R=min(R,a[i].r);
}
if(L<=R)ok();
L=0,R=INF;
for(int i=1;i<=n;i++){
L=max(L,a[i].x),R=min(R,a[i].y);
}
if(L<=R)ok();
}
vec O,p[N],q[N];
bool cmp1(const vec &a,const vec &b){
ll t=cross(a-O,b-O);
if(t)return t>0;
return dis2(a)>dis2(b);
}
bool cmp2(const vec &a,const vec &b){
ll t=cross(a-O,b-O);
if(t)return t<0;
return dis2(a)>dis2(b);
}
int t1,t2,s1[N],s2[N];
bool chkA(vec a,vec b,vec c){
return cross(b-a,c-a)>0;
}
bool chkB(vec a,vec b,vec c){
return cross(b-a,c-a)<0;
}
void chk2(){
for(int i=1;i<=n;i++){
p[i]=vec(a[i].l,a[i].y);
q[i]=vec(a[i].r,a[i].x);
}
O=vec(0,INF);
sort(p+1,p+1+n,cmp1);
O=vec(INF,0);
sort(q+1,q+1+n,cmp2);
for(int i=1;i<=n;i++){
for(;t1>1&&!chkA(p[s1[t1-1]],p[s1[t1]],p[i]);t1--);
s1[++t1]=i;
}
for(int i=1;i<=n;i++){
for(;t2>1&&!chkB(q[s2[t2-1]],q[s2[t2]],q[i]);t2--);
s2[++t2]=i;
}
for(int i=1;i<=t1;i++)p[i]=p[s1[i]];
for(int i=1;i<=t2;i++)q[i]=q[s2[i]];
// debug(ary(p,1,t1),ary(q,1,t2));
auto chkp=[&](vec x){
int k=lower_bound(p+1,p+1+t1,x,cmp1)-p;
if(k==1){
return cross(p[k+1]-p[k],x-p[k])<=0;
}else if(k<=t1){
return cross(p[k]-p[k-1],x-p[k-1])<=0;
}else{
return cross(p[t1]-p[t1-1],x-p[t1-1])<=0;
}
};
auto chkq=[&](vec x){
int k=lower_bound(q+1,q+1+t2,x,cmp2)-q;
if(k==1){
return cross(q[k+1]-q[k],x-q[k])>=0;
}else if(k<=t2){
return cross(q[k]-q[k-1],x-q[k-1])>=0;
}else{
return cross(q[t2]-q[t2-1],x-q[t2-1])>=0;
}
};
for(int i=1;i<=t1;i++)if(!chkq(p[i]))return;
for(int i=1;i<=t2;i++)if(!chkp(q[i]))return;
ok();
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d%d%d",&a[i].l,&a[i].x,&a[i].r,&a[i].y);
chk1(),chk2();
for(int i=1;i<=n;i++){
a[i].l=INF-1-a[i].l,a[i].r=INF-1-a[i].r;
}
chk2();
puts("impossible");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7964kb
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: 0
Accepted
time: 1ms
memory: 7776kb
input:
4 1 1 2 2 1 3 2 4 3 1 4 2 3 3 4 4
output:
impossible
result:
ok single line: 'impossible'
Test #3:
score: 0
Accepted
time: 1ms
memory: 9760kb
input:
3 1 1 2 2 1 3 2 4 3 3 4 4
output:
possible
result:
ok single line: 'possible'
Test #4:
score: 0
Accepted
time: 1ms
memory: 9864kb
input:
5 0 0 1 999999999 0 999999999 999999999 1000000000 1 0 999999998 1 999999998 0 999999999 999999999 2 999999998 3 999999999
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 8160kb
input:
4 0 1 1 1000000000 1 0 999999999 1 999999999 0 1000000000 999999999 2 999999999 999999999 1000000000
output:
impossible
result:
wrong answer 1st lines differ - expected: 'possible', found: 'impossible'