QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201943#5155. Faster Than LightPhantomThreshold#WA 449ms90368kbC++146.6kb2023-10-05 17:48:552023-10-05 17:48:56

Judging History

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

  • [2023-10-05 17:48:56]
  • 评测
  • 测评结果:WA
  • 用时:449ms
  • 内存:90368kb
  • [2023-10-05 17:48:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef __int128 ll;
struct frac{
	ll p,q;
	inline frac(){p=0;q=1;}
	inline frac(ll x){p=x,q=1;}
	inline frac(ll x,ll y){ll d=__gcd(x,y);p=x/d,q=y/d;if(q<0) p=-p,q=-q;}
	inline frac operator + (const frac &x) const{return frac(p*x.q+q*x.p,q*x.q);}
	inline frac operator - (const frac &x) const{return frac(p*x.q-q*x.p,q*x.q);}
	inline frac operator - () const{return frac(-p,q);}
	inline frac operator * (const frac &x) const{return frac(p*x.p,q*x.q);}
	inline frac operator / (const frac &x) const{return frac(p*x.q,q*x.p);}
	
	inline bool operator < (const frac &x) const{return p*x.q<q*x.p;}
	inline bool operator == (const frac &x) const{return p*x.q==q*x.p;}
	inline bool operator > (const frac &x) const{return p*x.q>q*x.p;}
	inline bool operator != (const frac &x) const{return p*x.q!=q*x.p;}
};

typedef long double db;

const db INF=1e9;
const db eps=1e-15;
int sign(db k){
	if (k>eps) return 1;
	else if (k<-eps) return -1;
	return 0;	
}
int cmp(db k1,db k2){return sign(k1-k2);}
int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}
struct point{
	db x,y;
	point operator + (const point &k1) const{return (point){x+k1.x,y+k1.y};}
	point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
	point operator * (db k1) const{return (point){x*k1,y*k1};}
	point operator / (db k1) const{return (point){x/k1,y/k1};}
	int operator == (const point &k1) const{return cmp(x,k1.x)==0 && cmp(y,k1.y)==0;}
	point turn90(){
		return (point){-y,x};
	}
	db abs2(){
		return x*x+y*y;	
	}
	int getP() const{
		return sign(y)==-1 || (sign(y)==0 && sign(x)==-1);	
	}
	/*
	void print(){
		cerr << "(" << x << "," << y << ") ";	
	}
	*/
};

db cross(point k1,point k2){
	return k1.x*k2.y-k1.y*k2.x;	
}
db dot(point k1,point k2){
	return k1.x*k2.x+k1.y*k2.y;	
}
int compareangle(point k1,point k2){
	return k1.getP()<k2.getP() || (k1.getP()==k2.getP() && sign(cross(k1,k2))>0);
}
point proj(point k1,point k2,point q){
	point k=k2-k1;
	return k1+k*(dot(q-k1,k)/k.abs2());
}
int checkLL(point k1,point k2,point k3,point k4){
	return cmp(cross(k3-k1,k4-k1),cross(k3-k2,k4-k2))!=0;	
}
point getLL(point k1,point k2,point k3,point k4){
	db w1=cross(k1-k3,k4-k3);
	db w2=cross(k4-k3,k2-k3);
	return (k1*w2+k2*w1)/(w1+w2);	
}

struct line{
	point p[2];
	line(point k1,point k2){p[0]=k1;p[1]=k2;}
	point& operator [](int k){return p[k];}
	int include(point k){return sign(cross(p[1]-p[0],k-p[0]))>=0;}
	point dir(){return p[1]-p[0];}
	/*
	void print(){
		p[0].print();
		cerr << "-> ";
		p[1].print();
		cerr << " ";
	}
	*/
};
point getLL(line k1,line k2){return getLL(k1[0],k1[1],k2[0],k2[1]);}
int parallel(line k1,line k2){return sign(cross(k1.dir(),k2.dir()))==0;}
int sameDir(line k1,line k2){
	return parallel(k1,k2) && sign(dot(k1.dir(),k2.dir()))==1;
}
int operator < (line k1,line k2){
	if (sameDir(k1,k2)) return k2.include(k1[0]);
	return compareangle(k1.dir(),k2.dir());	
}
int checkpos(line k1,line k2,line k3){
	return k3.include(getLL(k1,k2));	
}
vector<line> getHL(vector<line> &L){
	sort(L.begin(),L.end());
	
	deque<line> q;
	for (int i=0;i<(int)L.size();i++){
		if (i && sameDir(L[i],L[i-1])) continue;
		while (q.size()>1 && !checkpos(q[q.size()-2],q[q.size()-1],L[i])) q.pop_back();
		while (q.size()>1 && !checkpos(q[1],q[0],L[i])) q.pop_front();
		q.push_back(L[i]);
	}
	while (q.size()>2 && !checkpos(q[q.size()-2],q[q.size()-1],q[0])) q.pop_back();
	while (q.size()>2 && !checkpos(q[1],q[0],q[q.size()-1])) q.pop_front();
	vector<line> ans;
	for (int i=0;i<(int)q.size();i++) ans.push_back(q[i]);
	return ans;
}

const int maxn=400000;
int n;
point a[maxn+50];
point b[maxn+50];

void gao1(vector<line> &L,db x,db y){
	point P=(point){0,y};
	point Q=(point){1,y-x};
	point R=P+(Q-P).turn90();
	if (R.x*x+R.y>y) swap(P,Q);
	L.emplace_back(P,Q); 
}
void gao2(vector<line> &L,db x,db y){
	point P=(point){0,y};
	point Q=(point){1,y-x};
	point R=P+(Q-P).turn90();
	if (R.x*x+R.y<y) swap(P,Q);
	L.emplace_back(P,Q); 
}

bool checkXY(vector<pair<int,int>> &v){
	int sz=v.size();
	sort(v.begin(),v.end(),
		[&](const pair<int,int> &A,const pair<int,int> &B){
			return A.second<B.second;	
		}
	);
	int mxl=-1e9;
	for (int i=0;i<sz;i++) mxl=max(mxl,v[i].first);
	if (mxl<=v[0].second) return true;
	return false;
}

bool checkOK(vector<line> &L){
	if (L.size()<=2) return false;
	int sz=L.size();
	/*
	point O=(point){db(0),db(0)};
	for (int i=0;i<sz;i++){
		int nxt=(i+1)%sz;
		O=O+getLL(L[i],L[nxt]);
	}
	O=O/sz;
	*/
	point O=getLL(L[0],L[1]);
	/*
	for (int i=0;i<sz;i++){
		int nxt=(i+1)%sz;
		db lim=INF*db(2);
		if (L[i][0].x>lim || L[i][0].x<-lim) continue;
		if (L[i][0].y>lim || L[i][0].y<-lim) continue;
		if (L[i][1].x>lim || L[i][0].x<-lim) continue;
		if (L[i][1].y>lim || L[i][0].y<-lim) continue;
		
		if (L[nxt][0].x>lim || L[nxt][0].x<-lim) continue;
		if (L[nxt][0].y>lim || L[nxt][0].y<-lim) continue;
		if (L[nxt][1].x>lim || L[nxt][0].x<-lim) continue;
		if (L[nxt][1].y>lim || L[nxt][0].y<-lim) continue;
		
		O=getLL(L[i],L[nxt]);
		break;
	}
	*/
	for (int i=0;i<sz;i++){
		if (sign(cross(L[i][1]-L[i][0],O-L[i][0]))<0) return false;
	}
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);
	vector<pair<int,int>> vx;
	vector<pair<int,int>> vy; 
	cin >> n;
	for (int i=1;i<=n;i++){
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		a[i]=(point){db(x1),db(y1)};
		b[i]=(point){db(x2),db(y2)};
		vx.emplace_back(x1,x2);
		vy.emplace_back(y1,y2);
	}
	if (checkXY(vx) || checkXY(vy)){
		cout << "possible" << "\n";
		return 0;	
	}
	
	{
		vector<line> L;
		L.emplace_back((point){db(0),db(1)},(point){db(0),db(0)});
		L.emplace_back((point){db(INF),db(0)},(point){db(INF),db(1)});
		
		for (int i=1;i<=n;i++){
			gao1(L,a[i].x,b[i].y);
			gao2(L,b[i].x,a[i].y);
		}
		gao1(L,0,INF);
		gao2(L,INF,0);
		/*
		cerr << "----------------" << endl;
		for (auto l:L){
			l.print();
			cerr << endl;	
		}
		*/
		L=getHL(L);
		/*
		cerr << "----------------" << endl;
		for (auto l:L){
			l.print();
			cerr << endl;	
		}
		*/
		if (checkOK(L)){
			cout << "possible" << "\n";
			return 0;
		}
	}
	{
		vector<line> L;
		L.emplace_back((point){db(0),db(0)},(point){db(0),db(1)});
		L.emplace_back((point){db(-INF),db(1)},(point){db(-INF),db(0)});
		
		for (int i=1;i<=n;i++){
			gao1(L,b[i].x,b[i].y);
			gao2(L,a[i].x,a[i].y);
		}
		gao1(L,INF,INF);
		gao2(L,0,0);
		
		L=getHL(L);
		if (checkOK(L)){
			cout << "possible" << "\n";
			return 0;
		}
	}
	cout << "impossible" << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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: 1ms
memory: 5512kb

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

input:

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

output:

impossible

result:

ok single line: 'impossible'

Test #7:

score: 0
Accepted
time: 1ms
memory: 5504kb

input:

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

output:

possible

result:

ok single line: 'possible'

Test #8:

score: 0
Accepted
time: 430ms
memory: 85596kb

input:

199999
433914929 216935871 433914930 216935872
621822279 310889546 621822280 310889547
395914333 197935573 395914334 197935574
582775641 291366227 582775642 291366228
658726133 329341473 658726134 329341474
71689261 35823037 71689262 35823038
453260967 226608890 453260968 226608891
249802825 1248798...

output:

impossible

result:

ok single line: 'impossible'

Test #9:

score: 0
Accepted
time: 439ms
memory: 85848kb

input:

199999
783545903 638444708 783545904 638444709
129510863 105527268 129510864 105527269
844145756 687822366 844145757 687822367
69111161 56312696 69111162 56312697
820438487 668505332 820438488 668505333
541037357 440845152 541037358 440845153
201057677 163824672 201057678 163824673
132372296 1078588...

output:

impossible

result:

ok single line: 'impossible'

Test #10:

score: 0
Accepted
time: 449ms
memory: 73132kb

input:

199999
90035476 60020102 90035477 60020103
482291029 321523804 482291030 321523805
943496815 628994328 943496816 628994329
278866936 185907742 278866937 185907743
310938589 207288844 310938590 207288845
203677765 135781628 203677766 135781629
368744134 245825874 368744135 245825875
559390024 3729231...

output:

impossible

result:

ok single line: 'impossible'

Test #11:

score: 0
Accepted
time: 436ms
memory: 85644kb

input:

199999
207687261 415417709 207687262 415417710
150460947 300965081 150460948 300965082
9349830 18742847 9349831 18742848
87879837 175802861 87879838 175802862
354035800 708114787 354035801 708114788
305159254 610361695 305159255 610361696
248609913 497263013 248609914 497263014
499646110 999335407 4...

output:

impossible

result:

ok single line: 'impossible'

Test #12:

score: 0
Accepted
time: 434ms
memory: 73076kb

input:

199999
79738802 97861382 79738803 97861383
614827422 754561052 614827423 754561053
517213290 634761890 517213291 634761891
788424494 967612004 788424495 967612005
613541698 752983118 613541699 752983119
698980304 857839589 698980305 857839590
487475098 598265018 487475099 598265019
733711836 9004646...

output:

impossible

result:

ok single line: 'impossible'

Test #13:

score: -100
Wrong Answer
time: 256ms
memory: 90368kb

input:

199999
161399962 242105266 161399963 242105267
385751852 578633101 385751853 578633102
222705450 334063498 222705451 334063499
503730932 755601721 503730933 755601722
454037530 681061618 454037531 681061619
334605270 501913228 334605271 501913229
478675624 718018759 478675625 718018760
137316204 205...

output:

possible

result:

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