QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#698566 | #5067. Two Walls | wtz2333 | WA | 88ms | 3756kb | C++20 | 3.3kb | 2024-11-01 20:32:24 | 2024-11-01 20:32:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr double eps = 1e-7;
constexpr double PI = acos(-1);
constexpr double inf = 1e9;
struct Point { ll x, y; };
using Vec = Point;
struct Line { Point P; Vec v; };
struct Seg { Point A, B; };
Vec operator + (const Vec &a,const Vec &b){return (Vec){a.x + b.x,a.y + b.y};}
Vec operator - (const Vec &a,const Vec &b){return (Vec){a.x - b.x,a.y - b.y};}
ll operator * (const Point &a,const Point &b){return a.x * b.x + a.y * b.y;}// dot // 点乘
ll operator ^ (const Point &a,const Point &b){return a.x * b.y - a.y * b.x;}// cross // 叉乘
bool operator < (const Point& a, const Point& b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}
ll dis(Point a,Point b) { return (a - b) * (a - b);}
int sgn(ll x){
if(x == 0)
return 0;
if(x < 0)
return -1;
return 1;
}
Line line(Point A, Point B) { return {A, B - A}; }
// 线段与线段是否相交
bool cross_seg(Seg A,Seg B){ // 严格不交(不算端点)
Point a = A.A,b = A.B,c = B.A,d = B.B;
double c1 = (b - a) ^ (c - a),c2 = (b - a) ^ (d - a);
double d1 = (d - c) ^ (a - c),d2 = (d - c) ^ (b - c);
return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0;
}
int cross_ray_ray(Line A,Line B) {
if((A.v ^ B.v) == 0) {
if(((A.P - B.P) ^ A.v) == 0) {
if(sgn(A.v * (B.P - A.P)) < 0 && sgn(B.v * (A.P - B.P)) < 0) return -1;
else return 0;
}else return -1;
}
Vec v = B.P - A.P;
ll c1 = v ^ A.v;
ll c2 = v ^ B.v;
ll c = A.v ^ B.v;
if(sgn(c1) * sgn(c) >= 0 && sgn(c2) * sgn(c) >= 0) return 1; // 交
return -1;
}
void solve() {
Point A,B,C,D,E,F;
cin >> A.x >> A.y >> B.x >> B.y;
cin >> C.x >> C.y >> D.x >> D.y;
cin >> E.x >> E.y >> F.x >> F.y;
Seg s1 = {A,B};
Seg s2 = {C,D};
Seg s3 = {E,F};
if(!cross_seg(s1,s2) && !cross_seg(s1,s3)) {
cout << 0 << "\n";
return ;
}
if(!cross_seg(s2,s3)) {
cout << 1 << "\n";
return ;
}
auto calc = [&](Point a) {
if(sgn((E - C) ^ (D - C)) == sgn((a - C) ^ (D - C))) {
if(sgn((C - E) ^ (F - E)) == sgn((a - E) ^ (F - E))) return 1;
else return 2;
}else {
if(sgn((C - E) ^ (F - E)) == sgn((a - E) ^ (F - E))) return 4;
else return 3;
}
};
int flag1 = calc(A),flag2 = calc(B);
if(abs(flag1 - flag2) != 2) {
cout << 1 << "\n";
return ;
}
if(flag1 > flag2) {
swap(A,B);
swap(flag1,flag2);
}
if(flag1 == 1) {
Line l1 = line(A,C);
Line l2 = line(A,E);
Line l3 = line(B,F);
Line l4 = line(B,D);
if(cross_ray_ray(l1,l3) == 1 || cross_ray_ray(l2,l4) == 1) {
cout << 1 << "\n";
return ;
}
}else {
Line l1 = line(A,E);
Line l2 = line(A,D);
Line l3 = line(B,C);
Line l4 = line(B,F);
if(cross_ray_ray(l1,l3) == 1 || cross_ray_ray(l2,l4) == 1) {
cout << 1 << "\n";
return ;
}
}
cout << 2 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T --) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
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: 0ms
memory: 3616kb
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: 3756kb
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: 88ms
memory: 3684kb
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 2811th numbers differ - expected: '1', found: '2'