QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201888#5155. Faster Than LightPlentyOfPenalty#WA 1ms3532kbC++204.3kb2023-10-05 17:23:392023-10-05 17:23:39

Judging History

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

  • [2023-10-05 17:23:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3532kb
  • [2023-10-05 17:23:39]
  • 提交

answer

#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using V=long double;
const int N=2e5+9;
const V eps=1e-8,T=10,L=2e9;
int n;
int sgn(V x){
	if(fabsl(x)<eps)return 0;
	return x<0?-1:1;
}
struct point{
	V x,y;
	friend V operator^(const point &a,const point &b){return a.x*b.y-a.y*b.x;}
	friend V operator*(const point &a,const point &b){return a.x*b.x+a.y*b.y;}
	friend inline point operator+(const point &a,const point &b){return {a.x+b.x,a.y+b.y};}
	friend inline point operator-(const point &a,const point &b){return {a.x-b.x,a.y-b.y};}
};
struct line{
	point s,e;
	V angle;
	line(){}
	int x,y;
	line(point s,point e,int _x=-1,int _y=-1):s(s),e(e){
		x=_x,y=_y;
		angle=atan2l(e.y-s.y,e.x-s.x);
	}
	inline bool operator<(const line &rhs)const{
		return angle<rhs.angle;
	}
	point crosspoint(const line &v){
		V a1=(v.e-v.s)^(s-v.s);
		V a2=(v.e-v.s)^(e-v.s);
		return point{
			(s.x*a2-e.x*a1)/(a2-a1),
			(s.y*a2-e.y*a1)/(a2-a1)
		};
	}
	bool parallel(const line &v){
		return sgn((e-s)^(v.e-v.s))==0;
	}
};
struct rectangle{
	int x1,y1,x2,y2;
}a[N];
void FOUND(){
	cout<<"possible"<<endl;
	exit(0);
}
struct halfplanes{
	int n=0,st,ed;
	vector<line> hp;
	vector<point> p;
	vector<int> que;
	void push(const line &x){
		if(hp.size()<n+5){
			p.resize(n+5);
			hp.resize(n+5);
			que.resize(n+5);
		}
		hp[n++]=x;
	}
	void unique(){
		int m=1;
		for(int i=1;i<n;i++){
			if(sgn(hp[i].angle-hp[i-1].angle)!=0){
				hp[m++]=hp[i];
			}else if(sgn((hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s))>0){
				hp[m-1]=hp[i];
			}
		}
		n=m;
	}
	void debug(){
		fprintf(stderr,"st=%d ed=%d\n",st,ed);
		for(int i=st;i<=ed;i++)fprintf(stderr,"que[%d]=%d :: %d %d\n",i,que[i],hp[que[i]].x,hp[que[i]].y);
	}
	bool solve(){
		sort(hp.begin(),hp.begin()+n);
		// for(int i=0;i<n;i++)fprintf(stderr,"hp[%d]::%d %d::(%d,%d)->(%d,%d)\n",i,hp[i].x,hp[i].y,(int)hp[i].s.x,(int)hp[i].s.y,(int)hp[i].e.x,(int)hp[i].e.y);
		unique();
		que[st=0]=0;
		que[ed=1]=1;
		p[1]=hp[0].crosspoint(hp[1]);
		for(int i=2;i<n;i++){
			while(st<ed&&sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0)ed--;
			while(st<ed&&sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0)st++;
			que[++ed]=i;
			if(hp[i].parallel(hp[que[ed-1]]))return false;
			p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
			// debug();
		}
		while(st<ed&&sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0)ed--;
		while(st<ed&&sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0)st++;
		// debug();
		if(st+1>=ed)return false;
		return true;
	}
};
void check(){
	halfplanes sol;
	for(int i=1;i<=n;i++){
		// fprintf(stderr,"%d %d :: (%d,%d) -> (%d,%d)\n",i,1,1,a[i].y1-a[i].x1,0,a[i].y1);
		// fprintf(stderr,"%d %d :: (%d,%d) -> (%d,%d)\n",i,2,0,a[i].y2,1,a[i].y2-a[i].x2);
		// fprintf(stderr,"a[%d] :: %d %d %d %d\n",i,a[i].x1,a[i].y1,a[i].x2,a[i].y2);
		sol.push(line({1,(V)(a[i].y1-a[i].x1)},{0,(V)a[i].y1},i,1));
		sol.push(line({0,(V)a[i].y2},{1,(V)(a[i].y2-a[i].x2)},i,2));
	}
	sol.push(line({-L,-L-T},{L,-L}));
	sol.push(line({L-T,-L},{L,L}));
	sol.push(line({L,L-T},{-L,L}));
	sol.push(line({-L-T,L},{-L,-L}));
	if(sol.solve())FOUND();
}
void basic_check(vector<pair<int,int>> &a){
	vector<int> val;
	for(auto &it:a){
		val.push_back(it.first);
		val.push_back(it.second);
	}
	sort(all(val));
	val.erase(unique(all(val)),val.end());
	vector<int> ins(val.size()),del(val.size());
	for(auto &it:a){
		it.first=lower_bound(all(val),it.first)-val.begin();
		it.second=lower_bound(all(val),it.second)-val.begin();
		ins[it.first]++;
		del[it.second]++;
	}
	int cur=0;
	for(int i=0;i<val.size();i++){
		cur+=ins[i];
		if(cur==n)FOUND();
		cur-=del[i];
	}
}
int main(){
#ifdef memset0
	freopen("F.in","r",stdin);
#endif
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	vector<pair<int,int>> allx,ally;
	for(int i=1;i<=n;i++){
		cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2; 
		// a[i].x1+=T>>1;
		// a[i].y1+=T>>1;
		// a[i].x2+=T>>1;
		// a[i].y2+=T>>1;
		allx.emplace_back(a[i].x1,a[i].x2);
		ally.emplace_back(a[i].y1,a[i].y2);
		swap(a[i].y1,a[i].y2);
	}
	basic_check(allx);
	basic_check(ally);
	check();
	for(int i=1;i<=n;i++){
		a[i].y1=-a[i].y1;
		a[i].y2=-a[i].y2;
		swap(a[i].y1,a[i].y2);
	}
	check();
	cout<<"impossible"<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3464kb

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

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

input:

3
1 1 2 2
1 3 2 4
3 3 4 4

output:

possible

result:

ok single line: 'possible'

Test #4:

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

input:

5
0 0 1 999999999
0 999999999 999999999 1000000000
1 0 999999998 1
999999998 0 999999999 999999999
2 999999998 3 999999999

output:

possible

result:

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