QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#297144#5067. Two WallszzuqyWA 81ms3872kbC++144.6kb2024-01-04 00:35:002024-01-04 00:35:01

Judging History

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

  • [2024-01-04 00:35:01]
  • 评测
  • 测评结果:WA
  • 用时:81ms
  • 内存:3872kb
  • [2024-01-04 00:35:00]
  • 提交

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-8
#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 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) {
//	cout << a.x << ' ' << a.y << endl;
//	cout << b.x << ' ' << b.y << endl;
//	cout << c.x << ' ' << c.y << endl;
//	cout << d.x << ' ' << d.y << endl;
//	cout << sign ((d - c) ^ (b - a)) << endl;
	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 main() {
	//freopen("1.in", "r", stdin);
	int $;
	scanf("%d", &$);
	for(int WW=1;WW<=$;++WW)
	{
		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);
	//if(in(a,c1,c2)||in(a,d1,d2)||in(b,d1,d2)||in(b,c1,c2))cout<<"ww"<<endl;
	//if(b==c1||b==c2||b==d1||b==d2)cout<<"ww"<<endl;

		if (!check(a, b, c1, c2) && !check(a, b, d1, d2))
		{
			puts("0");continue;
		} 
		if (c1 == d1 || c2 == d1 || c1 == d2 || c2 == d2) 
		{
			puts("1");continue;
		} 
		
		if (!check(c1, c2, d1, d2))
		{
			puts("1");continue;
		} 
		if (check(a, b, c1, c2) + check(a, b, d1, d2) == 1) {
			puts("1");continue;
		}
		if(in(c1,d1,d2)||in(c2,d1,d2)||in(d1,c1,c2)||in(d2,c1,c2))
		{
			puts("1");continue;
		}
		 if (!sign((b - a) ^ (c2 - c1)) || !sign((b - a) ^ (d2 - d1))) {
			puts("1");continue;
		} 
		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;
			}
			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;
				}
			}
			if(WW==10029)cout<<"ww"<<ans<<a.x<<a.y<<b.x<<b.y<<c1.x<<c1.y<<c2.x<<c2.y<<d1.x<<d1.y<<d2.x<<d2.y<<endl;
			else printf("%d\n", ans);
		}
	}
	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: 3564kb

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

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

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: -100
Wrong Answer
time: 81ms
memory: 3620kb

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:

wrong output format Expected integer, but "ww2879262008-57033810728677252...941891602345381449897-485359180" found