QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#296990#5067. Two WallszzuqyWA 81ms3816kbC++146.0kb2024-01-03 21:01:202024-01-03 21:01:21

Judging History

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

  • [2024-01-03 21:01:21]
  • 评测
  • 测评结果:WA
  • 用时:81ms
  • 内存:3816kb
  • [2024-01-03 21:01:20]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <deque>
#include <utility>
using namespace std;
#define EPS 1e-14
#define double long double

struct Vector {
	long long x, y;
	inline Vector() {

	}
	inline Vector(long long x, long long y) {
		this->x = x;
		this->y = y;
	}
	inline Vector operator - (const Vector &a)const {
		return (Vector) {
			x - a.x, y - a.y
		};
	}
	inline long long operator * (const Vector &a)const {
		return x * a.x + y * a.y;
	}
	inline long long operator ^ (const Vector &a)const {
		return x * a.y - y * a.x;
	}
	inline double dis() {
		return std::sqrt(x * x + y * y);
	}
	inline int operator == (Vector a) {
		return a.x == x && a.y == y;
	}
};

inline int sign(long long a) {
	if (a == 0)
		return 0;
	return a > 0 ? 1 : -1;
}

inline int in(Vector a, Vector p, Vector q) {
	if (((p - a) ^ (q - a)))
		return 0;
	return ((p - a) * (q - a)) < 0;
}

inline int check(Vector a, Vector b, Vector c, Vector d) {
	if (!sign((d - c) ^ (b - a))) {
		if (in(a, c, d) || in(b, c, d) || in(c, a, b) || in(d, a, b)) {
			return 1;
		}
		return 0;
	}
	int cc = sign((c - a) ^ (c - b));
	int dd = sign((d - a) ^ (d - b));
	int aa = sign((a - c) ^ (a - d));
	int bb = sign((b - c) ^ (b - d));
	return  cc != dd &&  aa != bb;
}
int calc3(Vector a,Vector a0,Vector a1,Vector b,Vector b0,Vector b1){
	int ans = 2;
			if(check(a,b,b1,a0))ans=1;
			else
			if (!sign((b - a) ^ (b1 - a0))) {
				long long w1 = (b - a) * (b - a);
				long long w2 = (b1 - a0) * (b1 - a0);
				if (w1 > w2)
					ans = 1;
			} else {
				//cout<<((b - a) ^ (b1 - a0) )<<endl;

				if (((b - a) ^ (b1 - a0) ) > 0) {
					if(((b-a)^(a0-a))>0)
					{
						if (((b1 - b) ^ (a0 - a) ) < 0)
							ans = 1;
					}
					else
					if (((b1 - b) ^ (a0 - a) ) > 0)
							ans = 1;

				} else {
					if(((b-a)^(a0-a))<0)
					{
						if (((b1 - b) ^ (a0 - a) ) > 0)
							ans = 1;
					}
					else
					if (((b1 - b) ^ (a0 - a) ) < 0)
							ans = 1;
				}
			}
			//cout<<a0.x<<' '<<a0.y<<' '<<b1.x<<' '<<b1.y<<endl;
			//cout<<a1.x<<' '<<a1.y<<' '<<b0.x<<' '<<b0.y<<endl;
			//cout << sign((b - a) ^ (a1 - b0)) << endl;
			if(check(a,b,b0,a1))ans=1;
			else 
			if (!sign((b - a) ^ (b0 - a1))) {
				long long w1 = (b - a) * (b - a);
				long long w2 = (b0 - a1) * (b0 - a1);
				if (w1 > w2)
					ans = 1;
			} else {
				if (((b - a) ^ (b0 - a1) ) > 0) {
					if(((b-a)^(a1-a))>0)
					{
					if (((b0 - b) ^ (a1 - a) ) < 0)
						ans = 1;
					}
					else
					if (((b0 - b) ^ (a1 - a) ) > 0)
						ans = 1;
				} else {
					if(((b-a)^(a1-a))<0)
					{
					if (((b0 - b) ^ (a1 - a) ) > 0)
						ans = 1;
					}
					else if (((b0 - b) ^ (a1 - a) ) <0)
						ans = 1;
				}
			}
	return ans;
}
inline double dis(Vector x, Vector a, Vector b) {
	double len = (a - b) * (x - b) / std::sqrt((a - b).dis());
	return (x - b).dis() - len * len ;
}
bool compare2(Vector a,Vector b,Vector c){
	return ((double)(a * b)) /  b.dis() > EPS+((double)(a * c)) / c.dis();
}
bool compare1(Vector a,Vector b,Vector c){
	if(a.x==0&&a.y==0)return 0;
	long long tmp1=a^c;
	long long tmp2=a^b;
	double tmp3=a.x*(b.y+c.y/c.dis()*b.dis())-a.y*(b.x+c.x/c.dis()*b.dis());
	double tmp4=b.x*(b.y+c.y/c.dis()*b.dis())-b.y*(b.x+c.x/c.dis()*b.dis());
	//std::cout<<tmp1<<" "<<tmp2<<std::endl;
	//if(tmp1>0&&tmp2>0||tmp1<0&&tmp2<0)c=Vector(0,0)-c;
	if(tmp1==0){
		if(a.x>0&&b.x>0||a.x<0&&b.x<0||a.y>0&&b.y>0||a.y<0&&b.y<0){
			if(tmp2==0&&(a.x>0&&c.x>0||a.x<0&&c.x<0||a.y>0&&c.y>0||a.y<0&&c.y<0))return 0;
			return 1;
		}
		return 0;
	}
	if(tmp2==0){
		if(a.x>0&&c.x>0||a.x<0&&c.x<0||a.y>0&&c.y>0||a.y<0&&c.y<0){
			return 0;
		}
		return 1;
	}
	if(tmp1<0&&tmp2>0||tmp1>0&&tmp2<0){
		if(tmp3>0&&tmp1>0||tmp3<0&&tmp1<0)return 1;
		return 0;
	}
	else {
		//std::cout<<tmp3<<" "<<tmp4<<std::endl;
		//std::cout<<tmp1<<" "<<tmp2<<std::endl;
		if(tmp3>0&&tmp4>0||tmp3<0&&tmp4<0)return 1;
		return 0;
	}
}
int calc1(Vector a,Vector a0,Vector a1,Vector b,Vector b0,Vector b1){
	return 2-(compare1(b-a,a0-a,b1-b)||compare1(b-a,a1-a,b0-b));
}
int calc2(Vector a,Vector a0,Vector a1,Vector b,Vector b0,Vector b1){
	return 2-(compare2(b-a,a0-a,b1-b)||compare2(b-a,a1-a,b0-b));
}
int main() {
	//freopen("1.in", "r", stdin);
	int $;
	scanf("%d", &$);
	while ($--) {
		Vector a;
		Vector b;
		Vector c1;
		Vector c2;
		Vector d1;
		Vector d2;
		scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld", &a.x, &a.y, &b.x, &b.y, &c1.x, &c1.y, &c2.x, &c2.y, &d1.x,
		      &d1.y, &d2.x, &d2.y);

		//	cout << check(c1, c2, d1, d2) << endl;

		if (!check(a, b, c1, c2) && !check(a, b, d1, d2)) {
			puts("0");
		} else if (c1 == d1 || c2 == d1 || c1 == d2 || c2 == d2) {
			puts("1");
		} else if (!check(c1, c2, d1, d2)) {
			puts("1");
		} else if (check(a, b, c1, c2) + check(a, b, d1, d2) == 1) {
			puts("1");
		} else if (!sign((b - a) ^ (c2 - c1)) || !sign((b - a) ^ (d2 - d1))) {
			puts("1");
		} else {
			Vector a0(0, 0), a1(0, 0);
			Vector b0(0, 0), b1(0, 0);
			if (!check(a, c1, d1, d2)) {
				a0 = c1;
			} else {
				a0 = c2;
			}
			if (!check(a, d1, c1, c2)) {
				a1 = d1;
			} else {
				a1 = d2;
			}
			if (!check(b, c1, d1, d2)) {
				b0 = c1;
			} else {
				b0 = c2;
			}
			if (!check(b, d1, c1, c2)) {
				b1 = d1;
			} else {
				b1 = d2;
			}
//			printf("%lf %lf %lf %lf\n", dis(a, b, b1), dis(a0, b, b1), dis(a, b, b0), dis(a1, b, b0));
			
			int ans3=calc3(a,a0,a1,b,b0,b1);
			int ans1=calc1(a,a0,a1,b,b0,b1);
			int ans2=calc2(a,a0,a1,b,b0,b1);
			
			//std::cerr<<ans1<<" "<<ans2<<" "<<ans3<<std::endl;
			if(ans1==ans2&&ans2==ans3)putchar(ans1+'0'),putchar('\n');
			else putchar(3-(ans1^ans2^ans3)+'0'),putchar('\n'); 
		}
	}
	return 0;
}
/*
1
-999999999 999999998
999999999 999999998
-999999998 -999999998 1000000000 1000000000
999999998 -999999998 -1000000000 1000000000
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 1
2 2 3 3
4 4 5 5
0 0
1 1
2 2 3 3
2 2 3 3
0 0
10 10
10 0 0 10
1 1 2 2

output:

0
0
1

result:

ok 3 number(s): "0 0 1"

Test #2:

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

input:

2
-999999999 999999998
999999999 999999998
-1000000000 -1000000000 1000000000 1000000000
1000000000 -1000000000 -1000000000 1000000000
-999999999 999999998
999999999 999999998
-999999998 -999999998 1000000000 1000000000
999999998 -999999998 -1000000000 1000000000

output:

2
1

result:

ok 2 number(s): "2 1"

Test #3:

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

input:

1
0 0
1 1
2 2 3 3
4 4 5 5

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 81ms
memory: 3796kb

input:

100000
-851839419 34688642
-667081997 395784949
-624068418 -155389155 119194510 -758711821
-992436155 -812775173 851861070 -592596572
974613003 -179673992
-485749861 520596304
-115838823 -265233646 -573799007 -222234500
608830643 -887109945 483106217 -906910755
-597593284 384264657
940783 476657007
...

output:

0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
1
1
1
0
1
0
0
1
0
1
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
1
1
1
1
1
0
1
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
0
1
1
0
0
0
0
0
0
1
0
1
1
0
1
0
0
1
0
0
1
1
0
0
0
1
0
1
0
1
0
0
0
1
1
...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 74ms
memory: 3804kb

input:

100000
-496405053 -492673762
111401587 764822338
-588077735 774345046 959995351 -972693439
-729349041 -573156496 326664422 645305810
-477016787 -561855978
697257071 461011057
-416669921 377733217 784674141 -204150537
695471214 -642123788 -968584097 801626277
-329331824 68483816
945230774 982358552
-...

output:

1
1
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
1
1
0
1
1
0
1
1
1
0
0
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
1
0
1
0
1
0
0
0
0
1
1
0
1
1
0
0
0
1
1
1
1
1
1
0
1
1
0
0
0
0
0
1
0
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
0
0
0
0
1
0
1
0
0
1
1
0
1
0
1
0
1
0
0
1
1
1
0
0
0
0
0
0
0
1
1
1
1
...

result:

ok 100000 numbers

Test #6:

score: 0
Accepted
time: 81ms
memory: 3792kb

input:

100000
153996608 390029247
838007668 -918017777
-257119758 -244043252 390730779 813324945
-761229221 -38570526 634492154 -116791808
19475923 760994742
-119735998 991360398
-665623518 -632455126 -394909798 -481033868
-974798424 140919454 -715241704 510163308
-61070363 -542264319
-353569028 -511939904...

output:

1
0
0
1
1
1
0
0
0
1
1
0
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
0
1
0
0
0
1
1
0
0
1
0
0
1
1
0
0
0
1
0
0
0
1
0
1
1
0
1
0
1
0
1
1
1
0
0
0
1
0
0
0
0
0
1
1
1
0
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
1
1
0
0
1
0
0
0
0
1
0
0
1
0
1
1
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
0
0
0
...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 77ms
memory: 3608kb

input:

100000
509430974 -432300451
-140418957 -600857890
-464218867 442601156 -768468380 61286241
-203174812 201048150 404262799 826143280
567846134 673780049
525213848 983652653
-671487323 600446325 963563350 -462949905
-888157854 628995403 -166932017 218700340
207191097 898865049
590720963 288728935
4143...

output:

0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
1
0
1
1
0
1
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
1
0
1
1
0
0
0
1
1
0
0
0
0
0
0
1
0
1
0
1
0
0
0
1
1
1
0
0
0
1
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
1
1
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
1
1
0
0
0
0
0
0
1
1
1
0
1
0
0
1
0
0
0
0
0
1
1
0
1
0
...

result:

ok 100000 numbers

Test #8:

score: 0
Accepted
time: 78ms
memory: 3612kb

input:

100000
-840167367 450402558
586187125 -231820501
-428228185 -627664644 367299755 142271917
59912302 735634121 469000739 64045662
-935661158 291598063
-291779221 -780965301
-920440920 -409742018 -216020590 965199471
-801517283 -587961356 -156679415 465294457
423575055 583084208
-759956341 794430480
8...

output:

1
1
1
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
0
1
1
1
0
1
0
1
0
0
1
0
0
0
1
1
1
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
1
0
1
1
0
1
0
0
1
0
0
1
1
1
0
1
1
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
1
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
0
1
1
1
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 numbers

Test #9:

score: 0
Accepted
time: 65ms
memory: 3604kb

input:

100000
-779700294 -76959846
-340361999 380306679
-392237502 58979764 -201964817 -314799493
28032122 -729779910 -56195909 -454962165
-387290947 -142461426
891227711 -493705752
778727982 823159433 899362766 983283434
-471786920 -48007905 391630272 173831488
691836515 -322631221
236211152 -699867976
-3...

output:

0
0
0
0
0
1
0
0
1
1
0
1
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
1
0
1
0
0
0
0
0
1
0
1
1
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
1
1
1
1
0
0
0
1
0
0
0
0
0
1
1
0
0
1
0
0
0
1
0
1
0
0
0
0
0
1
0
0
1
1
1
1
0
1
0
0
0
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
1
0
1
1
0
0
0
...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 81ms
memory: 3612kb

input:

100000
-181176136 805743163
681211377 454376774
-599336611 988713965 638836024 -823748404
586086531 -490161233 251631822 782940218
-133888029 -524643413
74234642 -553290999
529774386 -533873706 -332098675 -998632604
-385146349 735035338 350005371 -412598775
960097976 -638412062
-819498858 -194166431...

output:

1
0
1
1
1
0
1
0
0
1
0
0
0
1
1
0
0
1
0
1
0
0
1
0
0
0
0
0
1
0
1
0
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
0
1
1
0
1
1
0
1
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
1
0
0
1
0
0
0
1
0
0
0
1
0
1
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
1
1
0
0
0
1
0
0
0
1
1
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
1
...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 77ms
memory: 3740kb

input:

100000
469225525 -311553829
-592182543 -933496047
-268378634 -29674334 -225395842 -985852520
849173645 44424737 21402468 20842600
657571974 -906825400
-742758427 -266031450
228943287 455937953 783284681 724484066
-593473073 -776888715 603347764 -460971951
-528550773 -954192903
-170176161 68445323
76...

output:

1
1
0
0
1
1
1
0
1
0
0
0
0
0
1
1
1
0
0
1
0
1
1
0
1
0
1
1
1
0
0
0
0
1
1
1
0
1
1
1
0
0
1
0
0
0
0
1
1
0
1
0
1
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
1
1
0
0
0
0
0
0
1
0
1
1
0
0
0
1
1
1
0
1
1
1
1
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
0
1
1
1
1
1
1
0
0
1
1
0
1
0
1
1
0
1
0
1
0
1
1
0
1
1
0
1
0
0
0
0
1
0
1
0
...

result:

ok 100000 numbers

Test #12:

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

input:

100000
824659891 866116474
429390833 -564458658
-232387951 656970075 910372293 505198569
817293465 579010708 86140408 963777688
616007597 416025321
440248505 -325616697
-20010310 -311160598 -101331964 742568030
-506832502 -236935264 -848342550 -752434920
-850223901 435058963
825991332 574146868
-776...

output:

1
0
0
0
1
1
1
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
0
1
0
0
1
1
0
0
1
0
1
1
0
0
0
1
1
0
0
1
0
0
1
1
0
1
0
1
1
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
0
1
1
0
0
1
1
0
0
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
0
1
0
1
1
1
...

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 76ms
memory: 3612kb

input:

100000
-181402541 -196228170
624722764 328251238
783857631 682518931 547715844 969228879
823684584 -149364638 -913952210 833196798
62726516 -554264004
664711179 426420047
-418659204 986117749 725195722 -692340474
963934566 206423874 688322091 -850621504
-259681786 -92095128
52318280 220754482
262610...

output:

1
1
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
1
1
0
0
0
0
1
1
0
1
1
0
1
1
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
1
0
1
1
0
0
1
1
1
1
0
0
0
0
1
0
0
1
0
1
0
0
0
1
1
1
0
0
0
1
1
0
0
0
0
0
1
1
0
0
1
0
1
0
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
1
0
0
1
0
1
0
0
1
0
0
1
1
0
0
1
0
1
0
1
1
1
...

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 76ms
memory: 3796kb

input:

100000
417121618 686474839
-353703861 697288626
-885184394 -630836661 -611483316 755247261
-618261009 -204713255 855818437 -223868114
316129433 -641478697
-152281890 661802094
-962580095 219019198 -159420924 -969223805
-654457570 989467117 -763368223 562948234
251669466 -702843263
996608271 -9785766...

output:

0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
1
1
1
1
0
0
0
0
0
1
1
0
1
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
1
1
1
0
0
1
1
0
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
1
0
1
0
0
1
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
1
1
0
1
0
0
0
0
1
1
0
0
0
1
0
0
1
1
1
0
0
0
0
1
0
1
...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 77ms
memory: 3800kb

input:

100000
-932476723 -135854859
667869515 -985551488
-849193711 593864833 819252113 298175852
-650141189 329872715 -836353833 -985965732
-892410565 976339317
-969274959 654094349
-968443900 -791169144 660995138 -951139842
-567817000 -470579434 -510025830 566452559
519930927 686408603
-302191531 -472875...

output:

1
0
1
1
0
0
1
1
0
0
0
1
0
0
1
1
1
0
0
0
0
0
1
0
1
1
1
1
1
1
0
0
1
1
0
1
0
1
1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
1
1
0
1
1
0
1
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
1
1
1
0
1
0
0
0
0
0
0
1
0
1
0
1
0
1
0
0
0
1
0
1
0
1
1
1
1
1
0
1
1
0
1
0
1
0
0
1
0
1
0
1
0
0
1
1
1
1
0
0
0
0
0
1
0
0
0
...

result:

ok 100000 numbers

Test #16:

score: 0
Accepted
time: 80ms
memory: 3796kb

input:

100000
-577042357 -958184557
-553646903 -616514099
-761325526 -719490759 -44979753 -210773060
-387054074 864458686 638449520 546903944
-639007648 299190036
213731973 889476396
782602504 -148202282 19468285 -933055879
-238086637 17496515 -204805935 518079383
493225093 127537970
642098459 32826410
215...

output:

0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
1
0
0
0
1
0
1
0
0
1
1
0
1
1
1
1
1
1
1
0
1
0
0
1
1
0
1
1
1
0
0
0
0
0
0
0
1
0
1
1
1
1
1
0
0
1
1
1
0
0
0
1
1
0
0
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1
0
0
0
1
0
1
0
0
0
0
1
1
0
1
0
0
0
1
0
1
0
0
0
1
0
1
1
1
1
0
1
1
0
0
1
0
0
0
1
0
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
1
1
...

result:

ok 100000 numbers

Test #17:

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

input:

100000
-516575284 219485746
172959179 -299354213
979697864 -32846351 795821088 -372877176
171000334 -895922639 703187460 -510160968
-142514938 -82991950
-308293802 881768651
776738700 -915300832 839884347 790060792
-151446066 800539757 48536459 226616414
709609051 -188242871
-656701343 538527956
912...

output:

0
0
1
1
1
1
0
0
1
1
0
0
0
1
1
0
0
0
0
1
1
0
0
0
1
1
0
0
1
0
1
1
1
1
0
1
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
1
1
0
0
1
1
0
0
1
0
1
0
0
0
1
0
0
1
1
1
1
0
0
1
1
0
1
0
0
0
1
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
1
1
0
0
0
1
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
0
1
0
0
0
0
1
0
1
...

result:

ok 100000 numbers

Test #18:

score: 0
Accepted
time: 77ms
memory: 3640kb

input:

100000
133826376 -897811246
-805467447 69683176
-984311454 896887850 226556516 -881826087
139120154 -361336668 472958105 727741414
110887979 -465173937
631623338 -882849303
475907601 74510826 -44732299 513177461
-359772790 -416417001 596846146 -64846555
977870511 -798991006
287588648 -955770500
-633...

output:

0
0
0
1
0
0
0
0
0
1
0
1
1
0
0
1
0
1
1
0
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
0
0
1
1
0
0
1
1
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
0
1
0
1
1
0
0
0
0
1
0
0
0
0
1
1
1
1
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
1
0
1
1
1
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
1
0
0
0
1
0
1
0
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
...

result:

ok 100000 numbers

Test #19:

score: 0
Accepted
time: 73ms
memory: 3628kb

input:

100000
489260742 -15108237
-78861365 681810357
-896443270 -416467743 -932642644 904192296
402207268 173249302 537696045 -329323498
902347982 -899233426
-480337024 -595589754
-68013290 -692587724 -981226446 531261424
-30042427 123536449 850188539 -356309523
-753868029 885228154
936911345 -450068955
1...

output:

1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
1
0
1
0
1
0
0
1
0
0
0
0
0
1
0
0
1
1
1
0
0
1
1
1
0
0
0
0
0
0
1
0
0
1
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
1
1
0
0
1
0
0
0
0
0
1
0
1
1
0
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
0
1
0
1
1
1
1
0
0
...

result:

ok 100000 numbers

Test #20:

score: 0
Accepted
time: 80ms
memory: 3604kb

input:

100000
-617247806 -542470641
699622219 998970243
-860452587 565143960 203125491 447120886
960261677 707835273 550556483 908578885
-844249102 718584588
702669908 -360207707
-73877095 297223934 -160810384 254378093
56598144 611612398 -601501775 -109715406
-780573863 569447313
-361888457 350599884
5702...

output:

1
1
0
0
1
1
0
0
0
0
1
0
1
1
1
0
0
1
0
0
1
1
0
1
1
0
1
0
0
0
1
1
1
1
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
0
0
0
0
1
1
0
1
1
1
1
0
1
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
0
1
1
0
1
0
1
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
0
1
1
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
...

result:

ok 100000 numbers

Test #21:

score: 0
Accepted
time: 72ms
memory: 3628kb

input:

100000
-261813440 340232368
-573771701 -631992369
-529494610 -505121840 -661106375 233139268
928381497 947453949 320327128 389571058
-52789098 336402602
-114323161 -124825660
-617797985 940190796 659605678 272462056
143238715 -605344361 -591249174 -401178375
-269222611 -41300822
877368828 856301429
...

output:

1
0
0
0
0
0
0
1
0
0
1
1
1
0
1
1
0
0
1
1
1
1
1
0
0
0
0
0
0
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
1
1
0
0
1
1
0
1
1
0
1
1
0
1
0
1
0
0
1
0
0
1
1
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
1
1
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
...

result:

ok 100000 numbers

Test #22:

score: 0
Accepted
time: 80ms
memory: 3636kb

input:

100000
-201346367 -482097330
742768969 -19865188
-736593719 -113444726 474661760 -223932141
-808531390 -517960081 90097774 -667493854
200613819 -45779385
-931316230 -132533405
-623661790 -69997546 18078824 -4421275
767936371 -65390910 -337906780 -987608637
-961151 -652048957
-473308476 -637997027
-5...

output:

1
0
0
0
0
0
1
0
0
1
0
1
1
1
1
1
0
1
0
1
0
0
1
1
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
0
0
0
1
0
1
1
1
0
0
0
1
0
0
1
0
1
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
1
1
0
0
0
0
1
1
0
1
0
1
0
1
0
0
1
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
...

result:

ok 100000 numbers

Test #23:

score: 0
Accepted
time: 76ms
memory: 3576kb

input:

100000
889700307 83152852
81040013 -449413311
374958682 300600303 -247400099 -855076598
-624900532 -785317715 857266066 -410224840
872271274 -850603331
-975572718 973091933
421906561 -222540906 -675309230 591089749
-544630032 -809400213 70027428 -810848022
902977690 -179653965
-183689299 262567523
7...

output:

0
1
0
0
1
1
0
0
0
1
1
0
1
0
0
1
0
0
0
1
1
1
0
0
1
0
0
0
1
0
0
0
0
0
1
0
1
0
1
1
1
1
0
1
0
1
1
0
0
0
0
1
0
0
0
0
0
1
0
1
1
2
1
0
0
1
1
0
0
1
1
1
1
1
1
0
0
0
1
0
1
0
0
0
0
1
0
0
1
1
1
1
0
0
0
1
0
0
0
0
1
0
0
0
1
1
0
1
1
1
1
0
0
0
1
1
1
1
0
0
1
0
0
0
1
1
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
...

result:

ok 100000 numbers

Test #24:

score: 0
Accepted
time: 30ms
memory: 3628kb

input:

45369
0 0
0 -1
999999997 999999997 -999999997 -999999998
-999999997 -999999997 999999997 999999998
0 0
0 -1
999999997 999999997 -999999997 -1000000000
-999999997 -999999997 999999997 999999998
0 0
0 -1
999999997 999999997 -999999998 -999999997
-999999997 -999999997 999999997 999999998
0 0
0 -1
99999...

output:

1
0
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
2
1
1
2
2
1
1
2
1
1
1
1
0
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
2
1
1
2
2
1
1
2
1
1
1
2
1
1
2
2
1
1
2
1
1
1
1
0
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
2
1
1
2
2
1
1
2
1
1
1
2
1
1
2
2
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
0
0
...

result:

ok 45369 numbers

Test #25:

score: -100
Wrong Answer
time: 52ms
memory: 3628kb

input:

100000
-1 -1
0 -2
2 1 0 0
-1 1 1 -1
-2 -1
-2 -1
0 -1 -1 0
2 2 0 -2
0 2
1 -2
0 -2 -2 0
2 -1 -2 0
0 2
-2 -2
-2 0 2 1
1 2 1 0
1 0
1 -1
0 -1 2 0
2 2 1 2
2 1
0 0
-2 1 1 2
-1 1 -1 2
0 0
2 1
2 -2 -2 1
-2 -2 1 -2
-1 -1
1 2
-2 -2 0 1
-2 1 -1 -2
-2 1
-1 1
-1 2 2 0
-1 2 -2 -2
0 2
0 1
1 -2 1 0
1 1 0 0
2 1
1 -2
...

output:

0
0
1
1
1
0
0
0
1
0
1
1
0
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
0
0
0
0
0
1
1
0
0
0
1
0
0
1
1
1
0
0
1
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
0
1
0
1
1
0
0
0
0
1
0
1
0
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
0
0
1
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
...

result:

wrong answer 42060th numbers differ - expected: '1', found: '2'