QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#876077#7653. Balloon DartsSeptemperAC ✓5ms4224kbC++233.3kb2025-01-30 16:55:292025-01-30 16:55:30

Judging History

This is the latest submission verdict.

  • [2025-01-30 16:55:30]
  • Judged
  • Verdict: AC
  • Time: 5ms
  • Memory: 4224kb
  • [2025-01-30 16:55:29]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using ll =long long;
using ld =long long;
const int N=1e5;
const ld eps=1e-10;

ld sqr(ld x) {return x*x;}
struct point{
	ld x,y;
	point operator + (const point &a) const{
		return {x+a.x,y+a.y};
	}
	point operator - (const point &a) const{
		return {x-a.x,y-a.y};
	}
	point operator * (const ld a) const{
		return {x*a,y*a};
	}
	point operator / (const ld a) const{
		return {x/a,y/a};
	}
	point rotate (ld t) const{
		return {x*cos(t)-y*sin(t),
			    x*sin(t)-y*cos(t)};
	}
	point rot90() const{
		return {-y,x};
	}
	point unit() const{
		return *this/sqrt(sqr(x)+sqr(y));
	}
};
ld dis(const point &a,const point &b){
	return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
ld dot(const point &a,const point &b){
	return a.x*b.x+a.y*b.y;
}
ld det(const point &a,const point &b){
	return a.x*b.x-a.y*b.y;
}
int sgn(ld x){
	return x>eps ? 1:( x<-eps ? -1: 0);
}
bool turn_left(const point& a,const point &b,const point &c){
	return sgn(det(b-a,c-a))>0;
}
struct line{
	point s,t;
};
bool same_dir(const line &a,const line &b){
	return sgn(det(b.t-b.s,a.t-a.s))==0 && sgn(dot(b.t-b.s,a.t-a.s))>0;
}
bool operator == (const point &a,const point &b){
	return sgn(dot(a-b,a-b))==0;
}
bool point_on_segment(const point &a,const line &l){
	return sgn(det(l.s-a,a-l.t)) == 0 && sgn(dot(l.s-a,a-l.t)) <=0;
}
bool twoside(const point &a,const point &b,const line &c){
//	if(turn_left(c.s,c.t,a) && !turn_left(c.s,c.t,b)){
//		return 1;
//	}
//	else return 0;
	return sgn(det(a-c.s,c.t-c.s)) * sgn(det(b-c.s,c.t-c.s))<0;
}
bool inter_judge(const line &a,const line &b){
	if(point_on_segment(a.s,b) 
	|| point_on_segment(a.t,b)
	|| point_on_segment(b.s,a) 
	|| point_on_segment(b.t,a))
	return true;
	return twoside(a.s,a.t,b) && twoside(b.s,b.t,a);
}
point line_intersect(const line &a,const line &b){
	ld u=det(a.t-a.s,b.s-a.s);
	ld v=det(a.t-a.s,b.t-a.s);
	return (b.s*v+b.t*u)/(v+u);
}
ld point_to_line(const point &a,const line &l){
	return det(l.t-l.s,a-l.s) / dis(l.t,l.s);
}
ld point_to_segment(const point&a,const line &l){
	if(sgn(det(a-l.s,l.s-l.t))*sgn(det(a-l.t,l.s-l.t))<=0) return point_to_line(a,l);
	else return min(dis(a,l.s),dis(a,l.t));
}
vector<point>check(point &a,point &b,vector<point>&c){
	vector<point>num;
	for(int i=0;i<c.size();i++){
		if(c[i]==a || c[i]==b) continue;
		else {
			if((a.y-b.y)*(c[i].x-b.x)==(c[i].y-b.y)*(a.x-b.x))
			    continue;
		    else num.push_back(c[i]);
		}
	}
	return num;
}
bool sol(point &a,point &b,int k,vector<point>&c){
	auto num=check(a,b,c);
	if(num.size()){
		if(k*2>=num.size()) return 1;
		else if(k==0) return 0;
		else {
			for(int i=0;i<=k;i++){
				for(int j=i+1;j<=k;j++){
					if(sol(num[i],num[j],k-1,num)) return 1;
				}
			}
			return 0;
		}
	}
	else return 1;
}
inline void solve() {
	int n; cin >> n;
	int k=3;
	vector<point>a(n);
	for(int i=0;i<n;i++) cin >> a[i].x >> a[i].y;
	if(n<=6) cout << "possible";
	else {
		for(int i=0;i<=k;i++){
			for(int j=i+1;j<=k;j++){
				if(sol(a[i],a[j],2,a)) {cout << "possible";return;}
			}
		}
		cout << "impossible";
	}
}

int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T = 1;
//	std::cin >> T;
	while (T--) solve();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3712kb

input:

6
0 0
1 1
2 4
3 9
4 16
5 25

output:

possible

result:

ok single line: 'possible'

Test #2:

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

input:

7
0 0
1 1
2 4
3 9
4 16
5 25
6 36

output:

impossible

result:

ok single line: 'impossible'

Test #3:

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

input:

7
-1 -1
0 0
1 1
2 4
3 9
4 16
5 25

output:

possible

result:

ok single line: 'possible'

Test #4:

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

input:

15
0 0
1 1
5 5
17 17
1000000000 1000000000
-1000000000 -1000000000
1 0
2 0
4 0
8 0
16 0
32 0
64 0
64 1
64 2

output:

possible

result:

ok single line: 'possible'

Test #5:

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

input:

10
3239 9832
17823 9324
2 50
18 3949
283921 38439849
293 2930
5 63
29 2
0 0
34 24

output:

impossible

result:

ok single line: 'impossible'

Test #6:

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

input:

16
0 0
1 1
5 5
17 17
1000000000 1000000000
-1000000000 -1000000000
1 0
2 0
4 0
8 0
16 0
32 0
64 0
64 1
64 2
65 1

output:

impossible

result:

ok single line: 'impossible'

Test #7:

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

input:

9
1 1
2 2
3 3
4 5
4 6
4 7
5 3
6 2
7 1

output:

possible

result:

ok single line: 'possible'

Test #8:

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

input:

6
214665391 -242590653
-135848526 149751756
850947148 -148832597
100890800 88534424
441506783 -592782565
-312879373 26540367

output:

possible

result:

ok single line: 'possible'

Test #9:

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

input:

10
536265711 842410327
-931816048 -541902121
-887361 -360363871
181841099 -350552250
762294270 -393048666
-750624811 -353183369
-299506807 711627207
61876805 -987058631
-543096207 518410281
169781203 -256662759

output:

impossible

result:

ok single line: 'impossible'

Test #10:

score: 0
Accepted
time: 2ms
memory: 4132kb

input:

10000
-421960859 215619520
986361829 411975888
407792858 548834690
-108610441 -657557244
833812622 883587870
132336768 -850087640
-330675568 389120794
725762828 39813972
-493180700 -374517995
-335022543 679087083
-111607696 -872340826
-232030581 402965087
-203510583 323905127
-627113030 965427352
-7...

output:

impossible

result:

ok single line: 'impossible'

Test #11:

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

input:

9
-45158434 51984694
-998885 -22974375
77465182 -89175050
-58604819 65544870
66059002 -76044680
55189601 -61725205
-1400753 -32217339
442935 10187485
-41706371 46645290

output:

possible

result:

ok single line: 'possible'

Test #12:

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

input:

9000
3182924 34216350
44302805 -32795587
-36076340 26705858
40235858 -27394619
42862674 -31729516
3669988 39452288
-3488232 -37498577
49786634 -33897275
9694600 -6600571
-524616 -5639705
91270432 -62141563
-30269077 22406975
-76404982 52020421
61723224 -42024315
18689371 -13834993
-10236834 7577912
...

output:

possible

result:

ok single line: 'possible'

Test #13:

score: 0
Accepted
time: 2ms
memory: 4208kb

input:

9000
37467476 -402886
-50886032 -89050544
-52429504 -91751620
-42198696 -73847706
-15676484 6967325
30272136 52976250
58970378 -634100
38429880 67252302
-32341765 347751
18568732 -8252771
18981587 -204113
67821700 -30142979
-14951336 -26164826
-44148394 474704
23353280 40868252
19060204 -8471203
-72...

output:

possible

result:

ok single line: 'possible'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3968kb

input:

9000
-45324458 -32821151
-9149461 -4879705
59323714 -58366878
-38200426 37584292
-7522610 -5447399
21718606 -21368304
-9854851 -5255913
-20313612 19985975
-48712030 47926354
4015229 2141463
1865502 1350889
16285409 8685559
-47470294 46704646
-59967262 59000050
34382216 24897475
-19230286 18920122
21...

output:

possible

result:

ok single line: 'possible'

Test #15:

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

input:

10000
8632200 -8
8270608 9070998
-64890154 20964514
-29027011 -31836068
-64691180 -8
46268881 -14948405
-26218969 -28756280
47456115 -8
21615302 23707114
-2618638 -2872046
5427009 5952212
9780618 10727138
-39866909 12880081
-32146525 -8
562933804 -362174008
-1394254 450454
16107346 17666130
17731436...

output:

impossible

result:

ok single line: 'impossible'

Test #16:

score: 0
Accepted
time: 4ms
memory: 4224kb

input:

10000
-20222914 -24436014
-72999510 -25549834
13779830 16650635
21082598 25474813
23989886 28987786
15605198 18856288
-22171234 -26790234
-18483154 -22333804
55494490 19423066
26070177 22218890
-50857510 -17800134
-70831910 -24791174
-366178 -442458
-41363310 -14477164
-11771650 -14224070
-97556710 ...

output:

impossible

result:

ok single line: 'impossible'

Test #17:

score: 0
Accepted
time: 2ms
memory: 4136kb

input:

10000
32555986 -58742335
28402425 -47135953
9333806 -16841445
268364555 464647815
40447256 -67125247
26875442 -44601811
9877434 -17822339
-4286150 7733693
162867 -6026407
31037903 -51509725
-5722408 10325202
-40448533 67127339
73498 -2719754
733084 -27124436
21833705 -36234673
469686 -17378710
11988...

output:

impossible

result:

ok single line: 'impossible'

Test #18:

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

input:

10000
9453791 -65317069
9009556 -62247809
-8193476 56609503
-1553150 10730887
-3602032 24886799
-10971009 75799731
-9172773 63375555
7816386 -54004089
-2759454 19065351
-4485464 30990511
9101934 -62886057
1168404 -8072577
-2420324 16722271
-9524190 65803527
-3366027 23256219
3034609 -20966357
108676...

output:

possible

result:

ok single line: 'possible'

Test #19:

score: 0
Accepted
time: 2ms
memory: 3968kb

input:

10000
3845331 2721975
15750505 11149233
21150356 19548062
-17095034 -12100980
44128126 -40450778
17192038 12169644
4034723 2856039
-12975847 -9185151
-43168296 -30557334
-68822991 -48717399
-20279187 -14354931
30289367 21440787
-71228394 -50420100
-20293694 -14365200
59007798 41769564
24129855 17080...

output:

possible

result:

ok single line: 'possible'

Test #20:

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

input:

9020
-52339245 7950273
-53694411 8156121
8681066 -1318635
-37201028 5650797
74612096 -11333475
-32825139 4986105
-8952998 1359957
3430173 -521031
-6211777 943569
-46118706 7005381
2178102 -330843
44481417 -6756663
-13619923 2068857
-18628602 2829669
-53999351 8202441
-28032051 4258041
-12474028 1894...

output:

possible

result:

ok single line: 'possible'

Test #21:

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

input:

10000
5969342 3373987
8277231 4678446
20541498 11610423
5786584 3270689
2365587 1337082
-1080043 -610448
5809239 3283494
-14573246 -8237041
-901175133 719288983
-18502658 -10458013
224088519 195013761
-18384806 -10391401
-10048939 -5679824
-21502939 -12153824
20740471 11722886
10251633 -6834415
1277...

output:

impossible

result:

ok single line: 'impossible'

Test #22:

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

input:

9021
36385271 46391233
-35259129 -44955377
-18419169 -23484428
18677991 23814451
-34640009 -44165999
-31770849 -40507820
35850751 45709720
-10418889 -13284071
-33372409 -42549809
-19008209 -24235454
-31724609 -40448864
-35016649 -44646215
33851391 43160536
26327671 33567793
6273311 7998484
18171551 ...

output:

impossible

result:

ok single line: 'impossible'

Test #23:

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

input:

9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

output:

possible

result:

ok single line: 'possible'

Test #24:

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

input:

9
0 0
0 4
4 0
4 4
2 6
6 2
4 8
8 4
6 6

output:

possible

result:

ok single line: 'possible'

Test #25:

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

input:

9
0 0
-2 0
1 1
-1 -1
-1 1
1 -1
0 1
0 -1
1 0

output:

possible

result:

ok single line: 'possible'

Test #26:

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

input:

7
-1000000000 -1000000000
1000000000 999999999
999999999 999999998
-10 0
10 0
0 -10
0 10

output:

impossible

result:

ok single line: 'impossible'

Test #27:

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

input:

7
-1000000000 -1000000000
1000000000 999999999
999999999 999999998
1 1
1 -1
-1 1
-1 -1

output:

possible

result:

ok single line: 'possible'

Test #28:

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

input:

1000
643422 34224
-78205846 -4159886
-10022006 -533086
53801832 2861799
-64759052 -3444631
-7329094 -389846
-11375794 -605096
-56544674 -3007696
-47015706 -2500836
25318234 1346714
4373624 232639
89071948 4737869
1880368 100019
-86906768 -4622701
60794586 3233754
13664584 726839
-62558888 -3327601
-...

output:

possible

result:

ok single line: 'possible'

Test #29:

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

input:

2000
57980882 -56747266
-85182716 83370298
-10105977 16169554
-2669107 4270562
5539410 -5421570
-18780458 18380854
48654108 -47618934
-20136277 32218034
27865558 -44584902
-39828468 38981034
34903600 -34160990
32965023 -52744046
-2310392 3696618
36351200 -35577790
-15803067 25284898
-8225252 1316039...

output:

possible

result:

ok single line: 'possible'

Test #30:

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

input:

3000
5920653 -63153666
-2197083 23435518
3361227 -35853122
37862690 58250303
33686291 37054933
-19237359 -21161082
-5025813 53608638
-20746159 -22820762
25954625 39930203
41924475 64499203
5672610 8727103
4181229 -44599810
-55893375 -85989797
-14147709 -15562467
-26808809 -29489677
-17566359 -193229...

output:

possible

result:

ok single line: 'possible'

Test #31:

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

input:

10000
4 -35327234
4 -31296726
4 -36144386
4 -46645610
4 24565554
4 -33193230
4 -34936594
4 39385706
4 17764618
4 59507998
4 -1183854
4 -48792002
4 71451170
4 -58542270
4 34855194
4 62841206
4 -43038422
4 55731482
4 -33420242
4 42944178
4 -50426534
4 -56441402
4 25138594
4 48805678
4 62301074
4 58643...

output:

possible

result:

ok single line: 'possible'

Test #32:

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

input:

10000
29967380 37306311
-19809564 -24660905
-14094890 -17546719
-27056615 -33682744
-26459746 -32939703
12653965 15752876
307729 383072
2469903 3074758
-4023724 -5009145
23738108 29551503
-35424737 -44100202
-9614232 -11968757
-33835520 -42121789
-43815399 -54545720
-33261289 -41406930
41090086 5115...

output:

possible

result:

ok single line: 'possible'

Test #33:

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

input:

10000
-49473019 -47606110
25703294 24733361
6753250 6498413
-18762699 -18054670
-36909528 -35516713
2537683 2441924
-3479248 -3347953
-12937098 -12448903
23023773 22154954
-16656426 -16027879
-50912287 -48991066
45194468 43489019
15945040 15343343
-37439634 -36026815
46718006 44955065
404804 389531
...

output:

possible

result:

ok single line: 'possible'

Test #34:

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

input:

10000
12086715 20327662
6329469 10645021
12511931 21042798
10994833 18491315
-6776305 -11396508
4720675 7939322
-19627143 -33009281
3705529 6232031
780409 1312511
21154631 35578248
970093 1631525
4403149 7405301
21677945 36458367
13585707 22848694
4417317 7429129
17261335 29030432
5625997 9461909
97...

output:

possible

result:

ok single line: 'possible'

Test #35:

score: 0
Accepted
time: 2ms
memory: 3808kb

input:

10000
32043669 4179612
-44774652 -5840169
12734571 1661034
-13036170 -1700367
-38082204 -4967241
-1913922 -249639
56637339 7387482
-18529674 -2416911
16594707 2164530
45311748 5910231
56300205 7343508
-43477935 -5671032
21355362 2785485
22103046 2883009
60755121 7924584
14207100 1853103
10112364 131...

output:

possible

result:

ok single line: 'possible'

Test #36:

score: 0
Accepted
time: 2ms
memory: 3808kb

input:

10000
-8523625 -1784009
22965791 4806799
-14020143 -2934443
-40072123 -8387183
-75102847 -15719195
-58542601 -12253097
27062659 5664283
-81768707 -17114375
65995977 13813117
-46277367 -9685955
23502259 4919083
-9868923 -2065583
-34274519 -7173731
-22986417 -4811105
-24829827 -5196935
79559897 166520...

output:

possible

result:

ok single line: 'possible'

Test #37:

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

input:

10000
-33715343 17289924
42464371 -21776596
61436155 -31505716
69682861 -35734796
-7017035 3598484
46989229 -24097036
-16214951 8315364
21569965 -11061516
-38441675 19713684
-58858487 30183844
72616519 -37239236
-25038389 12840204
62794837 -32202476
37418707 -19189076
39075583 -20038756
-50897651 26...

output:

possible

result:

ok single line: 'possible'

Test #38:

score: 0
Accepted
time: 2ms
memory: 3812kb

input:

10000
95482831 6751304
-59837081 -4230912
-72182084 -5103791
32999476 2333289
-29678117 -2098460
16502710 1166851
-18520520 -1309539
-74386616 -5259667
-37098761 -2623152
75601354 5345543
85502146 6045599
-73353353 -5186608
84174358 5951715
7933369 560938
55318828 3911425
-14504981 -1025612
58294867...

output:

possible

result:

ok single line: 'possible'

Test #39:

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

input:

10000
-74993961 -59370216
16460151 13030956
48437751 38346556
-47303529 -37448624
-49666953 -39319668
-85886889 -67993784
69695511 55175616
-20523177 -16247512
-44256777 -35036612
-64183209 -50811704
48930711 38736816
-19882857 -15740592
8096247 6409532
-9775113 -7738628
-3532809 -2796804
44945271 3...

output:

possible

result:

ok single line: 'possible'

Test #40:

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

input:

9
6 5
6 7
6 9
8 7
10 9
4 7
2 9
11 6
-14 1

output:

possible

result:

ok single line: 'possible'

Test #41:

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

input:

6065
492093837 -660801984
-13876767 24999975
-677303914 -921247234
31511197 -40922164
-34419819 -48223644
-307411587 -418940940
-535048710 -728067546
-733889233 -998088952
14312225 -17774753
-449522808 -611925102
97975021 -130373176
-44354646 -61714938
-138087579 -189002364
410180089 -550557535
-549...

output:

possible

result:

ok single line: 'possible'

Test #42:

score: 0
Accepted
time: 2ms
memory: 3872kb

input:

6093
512340237 -582292077
759699855 -864188725
4717846 23682994
-901316239 -920886323
612555102 -696499217
-671715679 -686688618
37391246 161042194
-446603551 -457069214
-377550751 -386633814
-343024351 -351416114
393548958 -446914833
517228767 -587863157
769476915 -875330885
660462696 -751095801
-9...

output:

impossible

result:

ok single line: 'impossible'

Test #43:

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

input:

2326
303927604 -914563089
-77323935 489701277
-138300123 880229415
238967520 -718618716
68231724 -203614479
-92463997 -11366901
-145351791 925392533
-10175044 -2139219
-30865887 192156029
233218840 -701278506
-106567617 676995384
-153418777 -18202221
-70064865 443209832
-83753397 530879414
-24436425...

output:

impossible

result:

ok single line: 'impossible'

Test #44:

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

input:

5244
-77069048 274996869
-16572308 57090669
-348769514 172426704
-150673415 540116079
-224053720 804428229
-284094506 140327160
-188315831 675702159
672275933 32375563
-102500085 366598179
910246340 905652336
-107093356 383142909
-226966526 814920009
-469938185 292206720
-97794783 349649919
-6491809...

output:

impossible

result:

ok single line: 'impossible'

Test #45:

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

input:

5644
56549023 437289868
81753175 628917788
225361373 -650673031
-100741212 40170011
79826743 614271068
65258101 503505248
-798929703 324478924
22073917 175174608
-177756579 71531392
181335533 31583743
81592639 627697228
454822529 77749711
70997263 547140268
514450721 87815247
227056799 -655582399
89...

output:

impossible

result:

ok single line: 'impossible'

Test #46:

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

input:

4964
-368111244 -815689161
-48011412 206626593
600216456 313440669
529228216 276485749
-22160854 92834463
-410783064 -910054701
919663536 479737809
-43094215 -96938298
-97996783 426658278
93463056 49635969
-227249573 995618928
-115382999 503191038
-62538053 270571728
-57047669 246403488
-212494166 9...

output:

impossible

result:

ok single line: 'impossible'

Test #47:

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

input:

5334
660540838 248023503
75683734 29220927
700722914 -902870303
131036546 -167555175
219363290 -281561749
580488662 -747679536
30665246 -38002250
-39109057 -12250179
483709598 -622763242
-910173121 -262004175
-894478273 -257504103
757450300 284278581
725997229 272511582
283178306 -363930135
82120652...

output:

impossible

result:

ok single line: 'impossible'

Test #48:

score: 0
Accepted
time: 2ms
memory: 3936kb

input:

7931
299473696 844963123
363956056 206946279
369441116 210045879
352045640 200215719
375553040 213499719
229572086 131006079
-123220253 -191983578
535716792 304008039
300997976 849250403
851734606 482589279
884174818 500921199
258508671 729742473
-194192813 211560483
267654351 755466153
-440718176 4...

output:

impossible

result:

ok single line: 'impossible'

Test #49:

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

input:

5466
326966679 -447625081
424756683 -581848444
4460356 21992844
238112756 971224924
16523931 71002109
222493601 907770823
75064016 308826016
940792525 -332267751
694202535 -951681013
378702675 -518636218
227699986 928922190
951890377 -336196251
421168059 -576922816
734557442 -259263126
241627849 -84...

output:

impossible

result:

ok single line: 'impossible'

Test #50:

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

input:

5015
-246738690 -128070431
38510790 284962156
65200969 477513600
525776519 -623447261
-760567082 -392514303
-423575734 -219080335
-897266960 171865016
42486629 -49358651
-137466743 -71833179
-559540065 -289054931
-142417176 26417261
-754728123 -389509259
-849918776 162741761
-673587608 128765501
-50...

output:

impossible

result:

ok single line: 'impossible'

Test #51:

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

input:

3699
456671993 -290314469
208790687 -132210155
240274004 -152290928
-825240015 -30900759
-386732745 -15002034
31707865 534307167
803387003 -511457159
942471530 -600168422
93219017 -58495925
960803588 -611861024
235890251 -149494871
28658291 -17317631
935696639 -595847243
537173639 -341660243
3893216...

output:

possible

result:

ok single line: 'possible'

Test #52:

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

input:

4000
-334346104 -632635935
-299329430 -566554458
-166966704 944125363
-38996235 216600939
-508519950 -961326918
-36754884 203858643
361495176 33337563
-284777046 -539092026
-160242651 905898475
-69521301 390138875
-32272182 178374051
-115522362 651659331
-137888920 -261893103
846095250 76807731
-112...

output:

possible

result:

ok single line: 'possible'

Test #53:

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

input:

2919
34030220 -11279836
339336945 -121334961
80355779 -377117881
200582769 -946950612
332266684 -118786316
855465998 -307386046
925525857 -332640801
349620961 -125042081
-340507503 -945074110
688350738 -247145346
194075219 -68971891
125701939 -592042385
12038209 -53317148
26954709 -124015998
7307723...

output:

possible

result:

ok single line: 'possible'

Test #54:

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

input:

2749
281749723 -586012219
729388979 878239320
186847963 -388143019
226081493 273035886
382187419 -795423789
-459513999 -90926396
-749611800 -147735423
152446075 -316415434
694648900 836466019
-524558349 -103663846
267600124 322960075
-718390512 -141621447
326065135 393261484
130302331 -270245954
723...

output:

possible

result:

ok single line: 'possible'

Test #55:

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

input:

1599
101507 121504253
382696671 -182511536
76300703 -35702308
815026575 -389661845
220410671 -104752411
7026817 887611433
6656013 846591521
7561211 946728365
3973137 549800393
807236847 -385929407
3133375 456902357
764393343 -365400998
-869127 14128601
4005855 553419797
-890939 11715665
790359103 -3...

output:

possible

result:

ok single line: 'possible'

Test #56:

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

input:

2959
-938739876 -720947315
-136151226 -105851735
-239776596 -185269139
-905552666 -695512983
-327485651 -252488445
-419935736 -323341227
-289557411 -223420637
-980393211 -752869997
-885572611 -680200477
-149019736 -115714027
-123621361 -96248977
-320712751 -247297765
-776528921 -596630529
-246210851...

output:

possible

result:

ok single line: 'possible'

Test #57:

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

input:

827
-743839330 -7734447
-786327720 -8119587
-861592868 -8801835
-482839220 -5368587
-215769340 -2947707
-558104368 -6050835
-72522768 -1649235
-47029734 -1418151
-987844084 -9946251
-729271882 -7602399
-853095190 -8724807
-611518344 -6535011
-332308924 -4004091
-637011378 -6766095
-556890414 -603983...

output:

possible

result:

ok single line: 'possible'

Test #58:

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

input:

1108
-684635679 -670424168
-603250479 -590617928
-465799919 -455834056
-834746159 -817622344
-563462159 -551601544
-438671519 -429231976
-79672359 -77197784
-218027199 -212868392
-371754799 -363613512
-460374239 -450513640
-978526679 -958613368
-724423999 -709440552
-890811519 -872599976
-651177319 ...

output:

possible

result:

ok single line: 'possible'

Test #59:

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

input:

509
-465432201 639769563
-604644273 831006130
-143952777 198151099
-217146753 298698160
-418071393 574709700
-590292513 811291020
-484089489 665399206
-340571889 468248106
-132471369 182379011
-267377913 367701045
-420941745 578652722
-251590977 346014424
-666356841 915781103
-247285449 340099891
-3...

output:

possible

result:

ok single line: 'possible'

Test #60:

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

input:

956
553971825 249006726
841968567 377951400
675897453 303596442
294354324 132768279
386849628 174181167
54707400 25471251
253362087 114414840
635956299 285713604
600219477 269713170
312222735 140768496
877705389 393951834
954434448 428305707
610730307 274419180
777852504 349244739
383696379 17276936...

output:

impossible

result:

ok single line: 'impossible'

Test #61:

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

input:

10000
813636422 -456173554
655702100 -791647176
-475708967 62425399
647803700 741083301
-228866762 -613639857
417016093 -289560348
473328691 -580048428
-620528292 930199160
596096706 -742793759
-969934190 -1738138
-233654630 527254368
-412402043 -140507179
425723658 -435985634
342723944 -938924747
-...

output:

impossible

result:

ok single line: 'impossible'

Test #62:

score: 0
Accepted
time: 4ms
memory: 4128kb

input:

10000
-77776507 -669647737
346219138 247769234
-338804879 -35566602
-842857478 781185925
-380982022 325292959
281794819 468779933
-106707144 -855297871
43650394 -803106346
529786052 -275619355
123032985 -403360898
673964139 507986357
533294154 -23490753
953954862 -591277746
-675933280 -664879448
-50...

output:

impossible

result:

ok single line: 'impossible'

Test #63:

score: 0
Accepted
time: 2ms
memory: 4108kb

input:

10000
-308741442 308370515
824493955 720912830
-777343955 -333919207
591811706 -269719689
956539195 63452038
53126143 567390692
60370964 -953468545
332764325 -412795496
833665612 -233964207
-992999224 -169379365
105125169 -35507734
499553759 -988014150
377386852 -863405063
-655306771 11387397
310119...

output:

impossible

result:

ok single line: 'impossible'

Test #64:

score: 0
Accepted
time: 2ms
memory: 4096kb

input:

10000
-254459488 335965313
55919361 -264687612
403021259 -402027879
612897653 -120938447
384818927 263143080
-16951157 -281591408
305812790 -803327854
224666832 -7378941
-464462302 746817824
158394962 -847938439
29108399 976165725
-618258232 -411472299
695613444 -133481034
-219123267 -215367756
7447...

output:

impossible

result:

ok single line: 'impossible'

Test #65:

score: 0
Accepted
time: 5ms
memory: 4132kb

input:

10000
471984019 228877513
-284276007 928131831
495987149 893937314
-265620624 -890395934
201212661 749680663
-980054874 709285342
-326015103 971743401
-489003603 -568980595
624737404 60310882
-757168446 -290125235
514798247 137856568
941566822 318932491
-984014033 -757472905
-485781719 -549818448
70...

output:

impossible

result:

ok single line: 'impossible'

Test #66:

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

input:

4769
-70653249 -498483482
718395876 -446849727
-92226249 -652867578
-103815999 -735807970
-130208499 -924682130
2187347 -14194739
-49826124 -349437134
-20048499 -136337810
-18499374 -125251718
-123954624 -879927166
-79374249 -560894074
-121831749 -864735114
-56137374 -394602694
-91709874 -649172214
...

output:

possible

result:

ok single line: 'possible'

Test #67:

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

input:

3682
12831197 108328451
-176867626 89215399
-73364588 565950201
-30977749 15022813
-49128057 376724520
-91649800 708711213
95050535 854193263
-18681454 139013967
-639194701 324332749
-543304641 275567669
-80868425 624536088
109577449 985976299
-139196531 70057689
-70087050 540360963
-46023021 352482...

output:

possible

result:

ok single line: 'possible'

Test #68:

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

input:

4345
322702674 -267801411
197459311 583727806
37801318 -10182711
93871106 278999449
537840306 -445669019
309619331 913672114
149079406 441407269
294364406 868796269
307149486 906406501
572328018 -474182147
314994876 929485507
56097006 167878309
71497216 213181543
593628136 -173450277
982896018 -8136...

output:

possible

result:

ok single line: 'possible'

Test #69:

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

input:

2053
-235238217 -312240264
-346032109 -458843985
-684823349 -907136355
-511765121 -678143766
-642703357 -851402709
-620727709 -822324285
-329550373 -437035167
-224250393 -297701052
638999124 -151046441
601044549 -142023905
834394899 -197495793
-625305969 -828382290
-264539081 -351011496
921549849 -2...

output:

possible

result:

ok single line: 'possible'

Test #70:

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

input:

6498
-856746868 315832671
-530556121 195271668
-499013216 183613323
138709809 -517802303
-627411394 231069645
543662631 -34471641
-150185796 54685743
256932189 -15798065
-963992745 355471044
715200057 -45643169
254020347 -951654141
-711278412 262067127
34058745 -1283233
41455827 -151887621
-38620094...

output:

possible

result:

ok single line: 'possible'

Test #71:

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

input:

4787
-120083407 17758917
174895749 -504955983
55962459 -159142032
88118919 -252641106
89259219 -255956676
25630479 -70947870
134757189 -388247919
-408807709 62666625
-758444311 117048533
33722703 194784276
122458497 693443619
55734399 -158478918
30232061 175168277
64970829 -185335035
-423426661 6494...

output:

possible

result:

ok single line: 'possible'

Test #72:

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

input:

5365
-757701773 345084609
4301994 120895779
-156576323 70485465
-84395073 37512465
16591158 567116595
24831789 866334759
-757124323 344820825
-4654838 469469497
-6694541 731369011
-3689913 345572347
-2671546 214813201
-7234899 800751415
-6213563 669611047
-1495822 63849289
-985217073 449015505
-6649...

output:

possible

result:

ok single line: 'possible'

Test #73:

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

input:

2382
-10241526 19236063
-347534142 701480439
798920573 156669903
-81701826 163779363
-80272620 160888497
-449960572 908659169
-848221 -6263083
554593369 109022511
-470445858 950094915
42510325 9158799
-196991110 396975887
-90753464 182088181
-90671713 -331026994
-5477506 9599843
-308945580 623427057...

output:

possible

result:

ok single line: 'possible'

Test #74:

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

input:

2121
-779641300 -229109686
-8852775 -900584355
-767737954 -225624139
-3020915 -366936295
-8131466 -834580516
167963675 183925254
22738699 25338670
38099033 42112251
-8223548 -843006538
52062973 57360961
605034997 661209877
401161473 438578711
-566703666 -166757123
711160941 777100073
881521009 96313...

output:

possible

result:

ok single line: 'possible'

Test #75:

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

input:

3939
730024785 630891306
-702193973 274971201
-166685470 -604073714
-422465775 164974401
-642015058 251307201
358710609 310310442
-54336826 20216001
-111998264 -406759640
-268482739 -971363165
-145601246 -528000818
-881485637 345473601
-264200006 -955910858
-712984675 279214401
548719035 474357681
-...

output:

impossible

result:

ok single line: 'impossible'

Test #76:

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

input:

2922
7393749 -59251146
-21367036 -7592072
102916374 -941753211
653141602 418272636
663636463 424980259
-464649606 -151066602
822673972 526626546
847700179 542621647
-831256272 -269723916
-626387841 -203415417
-280148212 -91350176
106624749 -976013666
314884159 202080787
734678599 470385707
885643138...

output:

impossible

result:

ok single line: 'impossible'

Test #77:

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

input:

2530
349040703 621088673
98224137 176189309
391762206 696868235
222254307 396194489
174939094 312266587
103736589 185967317
-19618988 -337518819
122570800 219375511
375684221 668349045
-566976050 363763589
473070873 841093853
-842319010 540702291
247060341 440195525
-171432610 109582611
434483709 77...

output:

impossible

result:

ok single line: 'impossible'

Test #78:

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

input:

2962
-322790634 -263911077
49685808 -337544913
20704056 -136380545
144318297 -994395639
57284682 -390289229
235943181 250120587
69036429 -471858927
39789600 -268854641
91479615 -627638651
95102334 -652784197
137216856 145673937
5683026 -32118525
61702632 -420954529
113657724 -781578457
-211611110 -1...

output:

impossible

result:

ok single line: 'impossible'

Test #79:

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

input:

4641
298622520 -261349939
825427890 -725019769
171257307 58343054
-770313093 435636087
495547377 166775939
932815923 312985442
926286354 -813790745
162643698 -141667641
152287695 -132552764
239638329 -209434770
-417077156 235487181
264402684 -231231215
965909322 -848665057
334643400 -293053859
98437...

output:

impossible

result:

ok single line: 'impossible'

Test #80:

score: 0
Accepted
time: 2ms
memory: 3968kb

input:

5705
-407002790 -357930476
-167718395 -147887321
-261804368 -230475718
-694469621 -610268035
-911290583 -800592853
-599081420 -526536546
-637822703 -560543533
-147205868 -525782308
-285244472 -251051374
-955240778 -839172208
-452580770 -397938696
-846179183 -743438253
-6629283 -26375888
-162605715 -...

output:

impossible

result:

ok single line: 'impossible'

Test #81:

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

input:

2783
32286066 -41292932
203712673 425252079
-687711129 -64085501
358006497 745966449
-589323825 -55052473
223750946 -290840352
-947961417 -87979317
55493409 117164259
-874964385 -81277393
-229099341 -21979935
630895382 -821495601
452769633 942940629
142967073 298986579
-111669333 -11198579
-63534369...

output:

impossible

result:

ok single line: 'impossible'

Test #82:

score: 0
Accepted
time: 3ms
memory: 4040kb

input:

6310
333325513 -11945089
-116380407 186241851
-233374527 375936651
-157188548 -720652918
-188694876 303492861
-105084423 167926491
-82402705 -379654332
-133678347 -613454216
-279466176 450669861
-169422363 -776435048
453540913 -16612789
488804097 -17981981
-345426654 557618481
-1021240 -8581902
-428...

output:

impossible

result:

ok single line: 'impossible'

Test #83:

score: 0
Accepted
time: 2ms
memory: 4096kb

input:

3699
-505377129 -895011916
-246361124 -435372092
230067259 -842742549
-324876684 -574702780
128945739 -470586745
-278779607 -680974173
-343225429 -607263756
206716679 -756805808
-164858559 -290740780
-398833028 -973289727
256505519 -940042826
-119999276 -294363279
-285234092 -696690063
-197288899 -3...

output:

impossible

result:

ok single line: 'impossible'

Test #84:

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

input:

2029
232781419 -253099158
547427699 -595841794
-16349616 -354999645
225575779 -245250090
320450039 -348596152
-8197842 -166999833
270010559 -293652676
267008209 -290382231
826045779 -899339090
-15222243 -328999671
-39417402 -886999113
756991729 -824118855
-7504074 -150999849
214767319 -233476488
-33...

output:

possible

result:

ok single line: 'possible'

Test #85:

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

input:

2489
-92420443 -17748367
-709404943 -130017647
-183956668 -34404711
-197611243 -36889359
-496494718 -91275543
-335168443 -61919887
-959738818 -175569527
-274481443 -50877007
-864156793 -158176991
-255769618 -47472119
-345282943 -63760367
-904109068 -165446887
-639614893 -117318335
-146533018 -275949...

output:

possible

result:

ok single line: 'possible'

Test #86:

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

input:

1749
964291137 -306513353
165010641 -51886106
779822163 -394360537
433866897 -137535798
787752993 -250273495
338309553 -107094040
569104833 -180618625
248420865 -78458149
-190191 742018
365843025 -115865394
346923549 -175715974
135857553 -42598790
900316305 -286132854
847030167 -428305355
337040019 ...

output:

possible

result:

ok single line: 'possible'

Test #87:

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

input:

1088
-606569238 -268234691
-165620763 -72822416
-488982978 -216124751
-240092061 -105825378
-592268033 -989727543
-144063282 -63268927
-176773697 -296065287
-187109377 -313320567
-123028161 -206337831
-731994582 -323818627
-81685441 -137316711
-422350764 -186595785
-217082849 -363360879
-389034657 -...

output:

possible

result:

ok single line: 'possible'

Test #88:

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

input:

1307
-331508070 -347713079
-667501654 -699379203
-346999653 -165784743
-334999665 -160033545
-407224934 -426961783
-861526118 -902454007
-672999327 -322025622
-692346250 -725382684
-910032234 -953222708
-886370714 -928457488
-860999139 -412127724
-12999987 -5709732
-884999115 -423630120
-190999809 -...

output:

possible

result:

ok single line: 'possible'

Test #89:

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

input:

503
18536595 306999693
32364444 524999475
31730139 514999485
42259602 680999319
33125610 536999463
54691980 876999123
39976104 644999355
34140498 552999447
39341799 634999365
5216190 96999903
42767046 688999311
54311397 870999129
52915926 848999151
6865383 122999877
53550231 858999141
23991618 39299...

output:

possible

result:

ok single line: 'possible'

Test #90:

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

input:

3285
-897164037 -246201984
-628601589 -172857616
-647603649 -178047076
-196621425 -54883892
-419578929 -115773556
-904131459 -248104786
-795503016 -218438373
-12934845 -4719112
-40487832 -12243829
-919016406 -252169863
-393609447 -108681294
-424962846 -117243903
-18952164 -6362441
-811971468 -222935...

output:

possible

result:

ok single line: 'possible'

Test #91:

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

input:

556
-64491856 550888119
-101175844 859975559
-109280446 928262319
-22049335 193281139
-28874263 250785779
-95204032 809658999
-92644684 788094759
-105228145 894118939
-17783755 157340739
-95417311 811456019
-86033035 732387139
-14158012 126791399
-111413236 946232519
-62785624 536511959
-117385048 9...

output:

possible

result:

ok single line: 'possible'

Test #92:

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

input:

1219
-352218405 535125915
-55490105 83855865
-398076415 604867650
-309597431 470307126
-256725843 389899008
-198459195 301285980
-388365307 590098812
-441776401 671327421
-266976457 405488337
-3697529 5088729
-231908567 352156422
-387825801 589278321
-175799943 266825358
-637077573 968345163
-351139...

output:

possible

result:

ok single line: 'possible'

Test #93:

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

input:

1024
469100833 -372622569
918633993 -729504369
905929795 -719418579
316650457 -251593089
494509229 -392794149
396784629 -315211149
95792861 -76255509
944042389 -749675949
220880349 -175561749
633278161 -502962009
988995705 -785364129
218925857 -174010089
376262463 -298918719
870748939 -691488699
850...

output:

possible

result:

ok single line: 'possible'