QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201975#5155. Faster Than LightPhantomThreshold#WA 792ms83576kbC++205.6kb2023-10-05 18:00:112023-10-05 18:00:12

Judging History

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

  • [2023-10-05 18:00:12]
  • 评测
  • 测评结果:WA
  • 用时:792ms
  • 内存:83576kb
  • [2023-10-05 18:00:11]
  • 提交

answer

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

typedef long double db;
const db INF=1e9;
const db eps=1e-15;
int sign(db k,db typ=0){
	if(typ==0)
	{
		if (k>eps) return 1;
		else if (k<-eps) return -1;
		return 0;	
	}
	else
	{
		if (k/typ>eps) return 1;
		else if (k/typ<-eps) return -1;
		return 0;
	}
}
int cmp(db k1,db k2)
{
	return sign(k1-k2,max(abs(k1),abs(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){0-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=200000;
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;
	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)});
		L.emplace_back((point){db(0),db(-INF*INF)},(point){db(1),db(-INF*INF)});
		L.emplace_back((point){db(1),db(INF*INF)},(point){db(0),db(INF*INF)});
		
		for (int i=1;i<=n;i++){
			gao1(L,a[i].x,b[i].y);
			gao2(L,b[i].x,a[i].y);
		}
		/*
		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)});
		L.emplace_back((point){db(0),db(-INF*INF)},(point){db(1),db(-INF*INF)});
		L.emplace_back((point){db(1),db(INF*INF)},(point){db(0),db(INF*INF)});
		
		for (int i=1;i<=n;i++){
			gao1(L,b[i].x,b[i].y);
			gao2(L,a[i].x,a[i].y);
		}
		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: 5880kb

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

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

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

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

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

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

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: 732ms
memory: 83120kb

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: 741ms
memory: 83240kb

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: 743ms
memory: 69568kb

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: 736ms
memory: 82928kb

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: 722ms
memory: 68476kb

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

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:

impossible

result:

ok single line: 'impossible'

Test #14:

score: 0
Accepted
time: 735ms
memory: 83576kb

input:

199999
222639792 110935680 222639793 110935683
931931336 465581452 931931337 465581455
35474718 17353143 35474719 17353146
206777070 103004319 206777071 103004322
914064786 456648177 914064787 456648180
301496196 150363882 301496197 150363885
515345552 257288560 515345553 257288563
500949336 2500904...

output:

impossible

result:

ok single line: 'impossible'

Test #15:

score: 0
Accepted
time: 742ms
memory: 83068kb

input:

199999
14166026 11542586 14166027 11542589
212205815 172908340 212205816 172908343
997392464 812690054 997392465 812690057
766610585 624645560 766610586 624645563
843092432 686964102 843092433 686964105
362333537 295234632 362333538 295234635
724513967 590344612 724513968 590344615
903878693 7364936...

output:

impossible

result:

ok single line: 'impossible'

Test #16:

score: 0
Accepted
time: 733ms
memory: 78332kb

input:

199999
259728590 173148768 259728591 173148771
221053226 147365192 221053227 147365195
899826680 599880828 899826681 599880831
847582532 565051396 847582533 565051399
258078974 172049024 258078975 172049027
369519293 246342570 369519294 246342573
214263539 142838734 214263540 142838737
737461550 491...

output:

impossible

result:

ok single line: 'impossible'

Test #17:

score: 0
Accepted
time: 717ms
memory: 69716kb

input:

199999
310634507 622037446 310634510 622037447
14947597 30663626 14947600 30663627
99728538 200225508 99728541 200225509
184650291 370069014 184650294 370069015
166422010 333612452 166422013 333612453
302228792 605226016 302228795 605226017
386996090 774760612 386996093 774760613
326681088 654130608...

output:

impossible

result:

ok single line: 'impossible'

Test #18:

score: 0
Accepted
time: 721ms
memory: 69400kb

input:

199999
799006978 980599598 799006981 980599599
101833006 124976996 101833009 124976997
491420512 603107117 491420515 603107118
529582438 649942208 529582441 649942209
453375406 556415396 453375409 556415397
591719612 726201467 591719615 726201468
775042202 951188282 775042205 951188283
218921560 268...

output:

impossible

result:

ok single line: 'impossible'

Test #19:

score: 0
Accepted
time: 756ms
memory: 68136kb

input:

199999
354595980 531899408 354595983 531899409
57294868 85947740 57294871 85947741
297914740 446877548 297914743 446877549
306592118 459893615 306592121 459893616
648745732 973124036 648745735 973124037
267426974 401145899 267426977 401145900
363073104 544615094 363073107 544615095
512209740 7683200...

output:

impossible

result:

ok single line: 'impossible'

Test #20:

score: 0
Accepted
time: 726ms
memory: 68292kb

input:

200000
183486 13299 183487 13300
102571 78692 102572 78693
170699 23633 170700 23634
62500 111076 62501 111077
175314 19903 175315 19904
147075 42725 147076 42726
131050 55675 131051 55676
165234 28050 165235 28051
98541 81949 98542 81950
186747 10663 186748 10664
128558 57690 128559 57691
75090 100...

output:

possible

result:

ok single line: 'possible'

Test #21:

score: 0
Accepted
time: 716ms
memory: 69320kb

input:

200000
84832 76958 84833 76959
10067 59201 10068 59202
59229 70877 59230 70878
106141 82019 106142 82020
89100 77971 89101 77972
107123 82252 107124 82253
29040 63708 29041 63709
174481 98249 174482 98250
149793 92386 149794 92387
31435 64276 31436 64277
152941 93133 152942 93134
112041 83420 112042...

output:

impossible

result:

ok single line: 'impossible'

Test #22:

score: 0
Accepted
time: 712ms
memory: 68416kb

input:

200000
44135 36736 44136 36737
89083 45138 89084 45139
71165 41788 71166 41789
68851 41356 68852 41357
94251 46104 94252 46105
24076 32986 24077 32987
75127 42529 75128 42530
21105 32431 21106 32432
97018 46621 97019 46622
100975 47361 100976 47362
122230 51334 122231 51335
131723 53109 131724 53110...

output:

impossible

result:

ok single line: 'impossible'

Test #23:

score: 0
Accepted
time: 723ms
memory: 68528kb

input:

200000
12123595 65272337 12123596 65272338
47819779 50226819 47819780 50226820
34587193 55804197 34587194 55804198
31014123 57310204 31014124 57310205
55526647 46978466 55526648 46978467
63405174 43657760 63405175 43657761
92658071 31328012 92658072 31328013
69459554 41105911 69459555 41105912
13473...

output:

possible

result:

ok single line: 'possible'

Test #24:

score: 0
Accepted
time: 727ms
memory: 69020kb

input:

200000
25587435 13688997 25587436 13688998
67822058 7043790 67822059 7043791
50756536 9728884 50756537 9728885
50605565 9752638 50605566 9752639
948172 17565746 948173 17565747
99155430 2113788 99155431 2113789
2457571 17328257 2457572 17328258
55236107 9024067 55236108 9024068
6859008 16635734 6859...

output:

impossible

result:

ok single line: 'impossible'

Test #25:

score: 0
Accepted
time: 722ms
memory: 67956kb

input:

200000
308 141674 309 141675
30411 124142 30412 124143
26864 126208 26865 126209
153801 52285 153802 52286
90521 89137 90522 89138
159641 48883 159642 48884
188626 32004 188627 32005
22527 128734 22528 128735
132574 64646 132575 64647
45592 115301 45593 115302
47431 114231 47432 114232
173312 40922 ...

output:

impossible

result:

ok single line: 'impossible'

Test #26:

score: 0
Accepted
time: 792ms
memory: 68824kb

input:

200000
56156 97395 56157 97396
75189 41275 75190 41276
87911 3766 87912 3767
50380 114426 50381 114427
34447 161405 34448 161406
45750 128079 45751 128080
36895 154185 36896 154186
82967 18345 82968 18346
83297 17369 83298 17370
50841 113065 50842 113066
61613 81307 61614 81308
81748 21939 81749 219...

output:

possible

result:

ok single line: 'possible'

Test #27:

score: 0
Accepted
time: 687ms
memory: 68752kb

input:

200000
110235 130882 110236 130883
132712 187597 132713 187598
94392 90907 94393 90908
81558 58524 81559 58525
59674 3306 59675 3307
61359 7558 61360 7559
133389 189304 133390 189305
120581 156987 120582 156988
129825 180310 129826 180311
84642 66306 84643 66307
112281 136044 112282 136045
67009 218...

output:

impossible

result:

ok single line: 'impossible'

Test #28:

score: 0
Accepted
time: 718ms
memory: 68384kb

input:

200000
140230 53637 140231 53638
142915 28531 142916 28532
137051 83364 137052 83365
141400 42696 141401 42697
144324 15354 144325 15355
128421 164046 128422 164047
126285 184020 126286 184021
141765 39283 141766 39284
136961 84199 136962 84200
142007 37021 142008 37022
137086 83034 137087 83035
128...

output:

impossible

result:

ok single line: 'impossible'

Test #29:

score: 0
Accepted
time: 729ms
memory: 69880kb

input:

200000
55205759 10901341 55205760 10901342
60674231 25887846 60674232 25887847
78521510 74798826 78521511 74798827
58210191 19135073 58210192 19135074
53049049 4990815 53049050 4990816
78791227 75537993 78791228 75537994
80659297 80657493 80659298 80657494
82535491 85799256 82535492 85799257
7105544...

output:

impossible

result:

ok single line: 'impossible'

Test #30:

score: 0
Accepted
time: 719ms
memory: 68784kb

input:

200000
69507066 51970715 69507067 51970716
86474964 98135774 86474965 98135775
67094841 45407702 67094842 45407703
75120388 67243045 75120389 67243046
80620577 82207570 80620578 82207571
58416570 21796476 58416571 21796477
77617864 74038000 77617865 74038001
61095812 29085968 61095813 29085969
70495...

output:

impossible

result:

ok single line: 'impossible'

Test #31:

score: -100
Wrong Answer
time: 394ms
memory: 52148kb

input:

200000
115996 107127 115997 107128
130561 66339 130562 66340
145545 24378 145546 24379
123364 86492 123365 86493
136600 49428 136601 49429
94939 166093 94940 166094
95551 164379 95552 164380
109878 124258 109879 124259
149367 13674 149368 13675
142089 34056 142090 34057
145354 24913 145355 24914
127...

output:

possible

result:

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