QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398552#3769. 共线点SamponYW#AC ✓5ms3988kbC++142.1kb2024-04-25 14:57:572024-04-25 14:57:59

Judging History

This is the latest submission verdict.

  • [2024-04-25 14:57:59]
  • Judged
  • Verdict: AC
  • Time: 5ms
  • Memory: 3988kb
  • [2024-04-25 14:57:57]
  • Submitted

answer

#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 1000005
#define P 1000000007
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
  int s = 1;
  while(n) {
    if(n & 1) s = 1ll * s * p % P;
    p = 1ll * p * p % P, n >>= 1;
  }
  return s;
}
int a, aL, aR;
int b, bL, bR;
int c, cL, cR;
struct p {
  db x, y;
} ;
il db calc(p A, p B, int x) {
  db k = (B.y - A.y) / (B.x - A.x), b = A.y - A.x * k;
  return k * x + b;
}
il void WORK() {
  bool F = 0; db s;
  p AL = {a, aL}, AR = {a, aR};
  p BL = {b, bL}, BR = {b, bR};
  p CL = {c, cL}, CR = {c, cR};
  s = calc(AL, BL, c); if(s >= cL && s <= cR) F = 1;
  s = calc(AL, BR, c); if(s >= cL && s <= cR) F = 1;
  s = calc(AR, BL, c); if(s >= cL && s <= cR) F = 1;
  s = calc(AR, BR, c); if(s >= cL && s <= cR) F = 1;

  s = calc(AL, CL, b); if(s >= bL && s <= bR) F = 1;
  s = calc(AL, CR, b); if(s >= bL && s <= bR) F = 1;
  s = calc(AR, CL, b); if(s >= bL && s <= bR) F = 1;
  s = calc(AR, CR, b); if(s >= bL && s <= bR) F = 1;

  s = calc(BL, CL, a); if(s >= aL && s <= aR) F = 1;
  s = calc(BL, CR, a); if(s >= aL && s <= aR) F = 1;
  s = calc(BR, CL, a); if(s >= aL && s <= aR) F = 1;
  s = calc(BR, CR, a); if(s >= aL && s <= aR) F = 1;

  if(F) cout << "Yes\n"; else cout << "No\n";
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  while(cin >> aL >> aR >> a >> bL >> bR >> b >> cL >> cR >> c) WORK();
  cerr << 1.0 * clock() / CLOCKS_PER_SEC;
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 3988kb

input:

0 1 0
0 1 1
0 1 2
0 1 0
1 2 1
0 1 2
0 1 0
2 3 1
0 1 2
3 8 2
5 7 4
2 8 7
2 7 1
1 3 3
0 8 4
4 6 1
1 3 3
2 9 4
0 9 1
0 3 6
2 9 9
0 6 3
4 6 5
1 2 7
6 9 4
4 7 6
1 8 9
0 6 5
0 6 6
0 8 7
4 7 2
6 8 4
2 5 8
5 6 1
6 9 2
1 5 9
3 5 1
2 8 2
3 4 6
5 8 2
1 6 3
8 9 7
1 7 2
4 7 6
2 9 9
5 6 3
0 7 5
2 4 8
0 3 1
2 9 3
...

output:

Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Y...

result:

ok 10000 lines