QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#672353 | #5067. Two Walls | mobbb | WA | 91ms | 3744kb | C++20 | 5.3kb | 2024-10-24 16:33:08 | 2024-10-24 16:33:28 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define db ll
constexpr db EPS = 0;
int sign(db a){ return a < -EPS ? -1 : a > EPS; }
int cmp(db a,db b) {return sign(a - b);}
struct P {
db x,y;
P() {}
P(db _x,db _y) : x(_x),y(_y){}
P operator+(P p) {return {x + p.x,y + p.y};}
P operator-(P p) {return {x - p.x,y - p.y};}
P operator*(db d) {return {x * d,y * d};}
P operator/(db d) {return {x / d,y / d};}
bool operator < (P p) const{
int c = cmp(x,p.x);
if (c) return c == -1;
return cmp(y , p.y) == -1;
}
bool operator == (P o) const{
return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
}
db dot(P p){return x * p.x + y * p.y;}
// a * b == |a| * |b| * cos<a,b> ,大于0为锐角小于0为钝角等于0为直角
db det(P p){return {x * p.y - y * p.x};}
// a * b == |a| * |b| * sin<a,b> == - (b * a) ,a逆时针转多少度可以转到b
// 大于0 b在a的逆时针方向,等于0共线,小于0 b在a的顺时针方向
void read(){std::cin >> x >> y;}
void print(){std::cout << x << " " << y << "\n";}
db distTo(P p) {return (*this - p).abs();}
db alpha() {return atan2l(y,x);}
db abs() {return sqrtl(abs2());}
db abs2() {return x * x + y * y;}
P rot90() {return P(-y,x);} // 逆时针旋转90度
int quad(){return sign(y) == 1 || (sign(y) == 0 && sign(x) == 1);}
P unit() {return *this / abs();}
// P rot(db an){return {x * cosl(an) - y * sinl(an),x * sinl(an) + y * cosl(an)};}
};
#define cross(p1,p2,p3) ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x))
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3)) // 以p1为起点去考虑<p1,p2> <p1,p3>
// 大于p2在p3的逆时针方向,小于0在顺时针,等于0共线
// 两个直线是否相交
bool chkLL(P p1,P p2,P q1,P q2){
db a1 = cross(q1,q2,p1),a2 = -cross(q1,q2,p2);
return sign(a1 + a2) != 0;
}
// 求两直线交点
P isLL(P p1,P p2,P q1,P q2){
db a1 = cross(q1,q2,p1),a2 = -cross(q1,q2,p2);
return (p1 * a2 + p2 * a1) / (a1 + a2);
}
// 判断区间 [l1,r1] ,[l2,r2] 是否相交
bool intersect(db l1,db r1,db l2,db r2){
if (l1 > r1) std::swap(l1,r1);if (l2 > r2) std::swap(l2,r2);
return !(cmp(r1,l2) == -1 || cmp(r2,l1) == -1);
}
// 两线段是否相交
bool isSS(P p1,P p2,P q1,P q2){
return intersect(p1.x,p2.x,q1.x,q2.x) && intersect(p1.y,p2.y,q1.y,q2.y) &&
crossOp(p1,p2,q1) * crossOp(p1,p2,q2) <= 0 && crossOp(q1,q2,p1) * crossOp(q1,q2,p2) <= 0;
}
// 两线段是否严格相交
bool isSS_strict(P p1,P p2,P q1,P q2){
return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1) * crossOp(q1,q2,p2) < 0;
}
// m 在不在a和b之间
bool isMiddle(db a,db m,db b){
return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}
// 点m 在不在a和b之间
bool isMiddle(P a,P m,P b){
return isMiddle(a.x,m.x,b.x) && isMiddle(a.y,m.y,b.y);
}
// 点q在线段上
bool onSeg(P p1,P p2, P q){
return crossOp(p1,p2,q) == 0 && isMiddle(p1,q,p2);
}
// 点q严格在线段上
bool onSeg_strict(P p1,P p2,P q){
return crossOp(p1,p2,q) == 0 && sign((q - p1).dot(p1 - p2)) * sign((q - p2).dot(p1 - p2));
}
// 求 q 到 p1p2的投影
P proj(P p1,P p2,P q){
P dir = p2 - p1;
return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
// 求 q以直线p1p2为轴的反射
P refect(P p1,P p2,P q){
return proj(p1,p2,q) * 2 - q;
}
// 求q到线段p1p2的最短距离
db nearest(P p1,P p2,P q){
if (p1 == p2) return p1.distTo(q);
P h = proj(p1,p2,q);
if (isMiddle(p1,h,p2)){
return q.distTo(h);
}
return std::min(p1.distTo(q),p2.distTo(q));
}
// 求线段p1p2 与线段q1q2的距离
db disSS(P p1,P p2,P q1,P q2){
if(isSS(p1,p2,q2,q2)) return 0;
return std::min({nearest(p1,p2,q1),nearest(p1,p2,q2),nearest(q1,q2,p1),nearest(q1,q2,p2)});
}
// 极角排序
// sort(p,p + n,[&](P a,P b){
// int qa = a.quad,qb = b.quad;
// if (qa != qb) return qa < qb;
// return sign(a.det(b)) > 0;
// })
int solve(){
P a,b,c,d,e,f;
a.read(),b.read();
c.read(),d.read();
e.read(),f.read();
if (!isSS(a,b,c,d) && !isSS(a,b,e,f)){
return 0;
}
if (!isSS_strict(c,d,e,f)){
return 1;
}
if (crossOp(c,d,a) * crossOp(c,d,b) >= 0) {
return 1;
}
if (crossOp(e,f,a) * crossOp(e,f,b) >= 0){
return 1;
}
if (crossOp(e,f,a) > 0) {
std::swap(e,f);
}
if (crossOp(d,c,a) < 0){
std::swap(c,d);
}
if ((c - d).det(f - e) < 0){
std::swap(c,f);
std::swap(d,e);
}
P la = d - a,ra = e - a;
P lb = c - b,rb = f - b;
// c.print(),d.print(),e.print(),f.print();
std::vector<std::pair<P,int>> evt;
evt.push_back({la,1});
evt.push_back({ra,-1});
evt.push_back({lb,1});
evt.push_back({rb,-1});
auto cmp = [&](P a,P b){
int qa = a.quad(),qb = b.quad();
if (qa != qb) return qa < qb;
return sign(a.det(b)) > 0;
};
int cur = cmp(ra,la) + cmp(rb,lb);
// std::cerr << cur << '\n';
sort(evt.begin(),evt.end(),[&](std::pair<P,int> a,std::pair<P,int> b){
int qa = a.first.quad(),qb = b.first.quad();
if (qa != qb) return qa < qb;
if (sign(a.first.det(b.first)) == 0){
return a.second < b.second;
}
return sign(a.first.det(b.first)) > 0;
});
if (cur >= 2) return 1;
for (auto [a,b] : evt){
cur += b;
if (cur >= 2){
return 1;
}
}
return 2;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--){
std::cout << solve() << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3732kb
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: 3548kb
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: 3592kb
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: 91ms
memory: 3744kb
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 2 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 2 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 16th numbers differ - expected: '1', found: '2'