QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318944#5067. Two WallszlxFTHWA 1ms3752kbC++172.5kb2024-02-01 11:40:542024-02-01 11:40:54

Judging History

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

  • [2024-02-01 11:40:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3752kb
  • [2024-02-01 11:40:54]
  • 提交

answer

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

#define debug(...) fprintf(stderr, __VA_ARGS__)

using db = long double;
constexpr db eps = 1e-14;
int dcmp(db x) {return x < -eps ? -1 : x > eps;}
struct Point {
  db x, y;
  Point(db x = 0, db 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*(db p) {return Point(x * p, y * p);}
  db operator*(const Point &b) {return x * b.x + y * b.y;}
  db operator^(const Point &b) {return x * b.y - y * b.x;}
  db len() {return sqrt(*this * *this);}
  bool operator==(const Point &b) {
    return !dcmp(x - b.x) && !dcmp(y - b.y);
  }
  void read() {
    int _x, _y;
    cin >> _x >> _y;
    x = _x, y = _y;
  }
};
bool onLine(Point p, Point a, Point b) {
  return dcmp((p - a) ^ (p - b)) == 0;
}
bool onSeg(Point p, Point a, Point b) {
  return onLine(p, a, b) && dcmp((p - a) * (p - b)) <= 0;
}
Point inter(Point a, Point b, Point c, Point d) {
  Point x = b - a, y = d - c, z = a - c;
  return a + x * ((y ^ z) / (x ^ y));
}

void solve() {
  auto pd = [&](Point a, Point b, Point c, Point d) {
    Point p = b - a, q = d - c;
    if ((p ^ q) == 0) {
      if (onSeg(c, a, b) || onSeg(d, a, b)) return false;
      return true;
    }
    Point i = inter(a, b, c, d);
    return !onSeg(i, a, b) || !onSeg(i, c, d);
  };
  Point a, b, c1, c2, d1, d2;
  a.read();
  b.read();
  c1.read(), c2.read();
  d1.read(), d2.read();
  if (pd(a, b, c1, c2) && pd(a, b, d1, d2)) {
    cout << 0 << "\n";
    return;
  }
  if (c1 == c2 || d1 == d2 || dcmp((c2 - c1) ^ (d2 - d1)) == 0) {
    cout << 1 << "\n";
    return;
  }
  Point i = inter(c1, c2, d1, d2);
  if (!onSeg(i, c1, c2) || !onSeg(i, d1, d2)) {
    cout << 1 << "\n";
    return;
  }
  Point p = c2 - c1, q = d2 - d1;
  Point t1 = c1 + ((p.len() + eps) / p.len());
  Point t2 = c2 - ((p.len() + eps) / p.len());
  Point t3 = d1 + ((q.len() + eps) / q.len());
  Point t4 = d2 - ((q.len() + eps) / q.len());
  auto check = [&](Point a, Point b) {
    return pd(a, b, c1, c2) && pd(a, b, d1, d2);
  };
  if (check(a, t1) && check(t1, b)
      || check(a, t2) && check(t2, b)
      || check(a, t3) && check(t3, b)
      || check(a, t4) && check(t4, b)) {
    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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:

1
1

result:

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