QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#319102#5067. Two WallszlxFTHWA 92ms3708kbC++172.5kb2024-02-01 20:38:032024-02-01 20:38:03

Judging History

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

  • [2024-02-01 20:38:03]
  • 评测
  • 测评结果:WA
  • 用时:92ms
  • 内存:3708kb
  • [2024-02-01 20:38:03]
  • 提交

answer

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

using i64 = long long;

struct Point {
  i64 x, y;
  Point(i64 x = 0, i64 y = 0) : x(x), y(y) {}
  Point operator+(const Point &b) {return Point(x + b.x, y + b.y);}
  Point operator-(const Point &b) {return Point(x - b.x, y - b.y);}
  Point operator*(i64 p) {return Point(x * p, y * p);}
  i64 operator*(const Point &b) {return x * b.x + y * b.y;}
  i64 operator^(const Point &b) {return x * b.y - y * b.x;}
  bool operator==(const Point &b) {
    return x == b.x && y == b.y;
  }
  void read() {
    int _x, _y;
    cin >> _x >> _y;
    x = _x, y = _y;
  }
};
bool onLine(Point p, Point a, Point b) {
  return ((p - a) ^ (p - b)) == 0;
}
bool onSeg(Point p, Point a, Point b) {
  return onLine(p, a, b) && (p - a) * (p - b) <= 0;
}

void solve() {
  auto icmp = [&](i64 x) {
    return x < 0 ? -1 : x > 0;
  };
  auto pd = [&](Point a, Point b, Point c, Point d) {
    if (onSeg(c, a, b) || onSeg(d, a, b)) return 1;
    Point x = b - a, y = d - c;
    if (icmp(x ^ (c - a)) * icmp(x ^ (d - a)) < 0 && icmp(y ^ (a - c)) * icmp(y ^ (b - c)) < 0) {
      return 2;
    } else {
      return 0;
    }
  };
  auto check2 = [&](Point a, Point b, Point c, Point d) {
    if (((b - a) ^ (d - c)) == 0) return 0;
    if (icmp((b - d) * (c - d)) < 0 || icmp((d - b) * (a - b)) < 0) return 1;
    return 0;
  };
  Point a, b, c1, c2, d1, d2;
  a.read();
  b.read();
  c1.read(), c2.read();
  d1.read(), d2.read();
  if (a == b || pd(a, b, c1, c2) == 0 && pd(a, b, d1, d2) == 0) {
    cout << 0 << "\n";
  } else {
    if (((c2 - c1) ^ (b - a)) == 0 || ((d2 - d1) ^ (b - a)) == 0) {
      cout << 1 << "\n";
    } else {
      auto check = [&](Point a, Point b) {
        return pd(a, b, c1, c2) != 2 && pd(a, b, d1, d2) != 2;
      };
      if (check(a, c1) && check(c1, b)
          || check(a, c2) && check(c2, b)
          || check(a, d1) && check(d1, b)
          || check(a, d2) && check(d2, b)) {
        cout << 1 << "\n";
      } else {
        if (check(a, c1) && check(b, d1) && check2(a, c1, b, d1)
            || check(a, c1) && check(b, d2) && check2(a, c1, b, d2)
            || check(a, c2) && check(b, d1) && check2(a, c2, b, d1)
            || check(a, c2) && check(b, d2) && check2(a, c2, b, d2)) {
          cout << 1 << '\n';
        } else {
          cout << 2 << "\n";
        }
      }
    }
  }
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3560kb

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

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: 92ms
memory: 3708kb

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 296th numbers differ - expected: '1', found: '2'