QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#698537 | #5067. Two Walls | wtz2333 | WA | 1ms | 3688kb | C++20 | 3.3kb | 2024-11-01 20:18:44 | 2024-11-01 20:18:46 |
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(abs(x) < eps)
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((D - C) ^ (A - C)) > 0) {
if(sgn((A - E) ^ (F - E)) > 0) return 1;
else return 2;
} else {
if(sgn((A - E) ^ (F - E)) > 0) 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();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3688kb
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: 1ms
memory: 3612kb
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'