QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#210182#5155. Faster Than Lightucup-team1004WA 2ms6872kbC++143.1kb2023-10-11 07:31:442023-10-11 07:31:45

Judging History

你现在查看的是最新测评结果

  • [2023-10-11 07:31:45]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:6872kb
  • [2023-10-11 07:31:44]
  • 提交

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-O)>dis2(b-O);
}
bool cmp2(const vec &a,const vec &b){
	ll t=cross(a-O,b-O);
	if(t)return t<0;
	return dis2(a-O)>dis2(b-O);
}
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(-INF,INF);
	sort(p+1,p+1+n,cmp1);
	O=vec(INF,-INF);
	sort(q+1,q+1+n,cmp2);
	t1=t2=0;
	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;
	}
	// debug(ary(p,1,n));
	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){
		O=vec(-INF,INF);
		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){
		O=vec(INF,-INF);
		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: 2ms
memory: 6648kb

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: 0ms
memory: 6664kb

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: 6760kb

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: 0ms
memory: 6632kb

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: 0
Accepted
time: 0ms
memory: 6636kb

input:

4
0 1 1 1000000000
1 0 999999999 1
999999999 0 1000000000 999999999
2 999999999 999999999 1000000000

output:

possible

result:

ok single line: 'possible'

Test #6:

score: 0
Accepted
time: 0ms
memory: 6872kb

input:

3
0 0 1 1000000000
2 0 999999999 1
2 999999999 999999999 1000000000

output:

impossible

result:

ok single line: 'impossible'

Test #7:

score: -100
Wrong Answer
time: 0ms
memory: 6716kb

input:

3
0 0 1 1000000000
2 0 999999999 1
2 999999999 1000000000 1000000000

output:

impossible

result:

wrong answer 1st lines differ - expected: 'possible', found: 'impossible'