QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297131 | #5067. Two Walls | zzuqy | WA | 80ms | 3696kb | C++14 | 4.5kb | 2024-01-04 00:22:35 | 2024-01-04 00:22:36 |
Judging History
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(WW==10029)
cout<<c1.x<<endl;
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;
}
}
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: 1ms
memory: 3696kb
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: 3628kb
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: 3512kb
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: 80ms
memory: 3624kb
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 answer 10029th numbers differ - expected: '1', found: '-846431435'