QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#672476 | #5067. Two Walls | qinglu09 | WA | 1ms | 3732kb | C++23 | 8.4kb | 2024-10-24 16:58:20 | 2024-10-24 16:58:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
#define endl '\n'
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
typedef pair<int,int> PII;
typedef long double ld;
#define ld double
const int N=1e5+10;
const ld eps=1e-12;
#define debug(x) cout<<#x<<": "<<x<<endl
const double pi = acos(-1.0);
const double pi1=pi/180,pi2=180/pi;
double dtopi(double x) {return x*pi1;}
double pitod(double x) {return x*pi2;}
int sgn(double x)
{
if(fabs(x)<eps) return 0; // x == 0, 精度范围内的近似相等
return x>0?1:-1; // 返回正负
}
typedef struct point
{
double x,y;
point(double x = 0, double y = 0) : x(x), y(y) {}
double operator * (point b) {return x*b.x+y*b.y;}//点乘
double operator ^ (point b) {return x*b.y-y*b.x;}//叉乘
point operator + (point b) {return point(x+b.x,y+b.y);}
point operator - (point b) {return point(x-b.x,y-b.y);}
bool operator == (const point &b) const {return sgn(x-b.x)==0&&sgn(y-b.y)==0;}
bool operator < (const point &b) const {return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;}
bool operator > (point b) {return !(*this<b);}
point operator * (double k) {return point(k*x,k*y);}//数乘
point operator / (double k) {return point(x/k,y/k);}//数除
double len() {return hypot(x,y);}//模长
double len2() {return x*x+y*y;}//模长平方
point trunc(double r) {double l=len();r/=l;return point(x*r,y*r);}//变模长为r
double dis(point b){return hypot(x-b.x,y-b.y);}
double angle() {return atan2(y,x);}
int quad() {return sgn(y)>0||sgn(y)==0&&sgn(x)>0;}//0:[-π,0) 1:[0,π)
point unit() {return *this/len();}//单位向量
}Vector;
double len(Vector a) {return sqrt(a*a);}//模长
double len2(Vector a) {return a*a;}//模长
double dis(point a,point b) {return (a-b).len();}
double dis2(point a,point b) {return (a-b).len2();}
double norm(double x)//返回弧度[0,2π)
{
while(x<0) x+=2*pi;
while(x>=2*pi) x-=2*pi;
return x;
}
double angle(Vector a,Vector b)//a到b的夹角
{
double t=acos((a*b)/len(a)/len(b));
return t; // 返回 [0,π]
//return pitod(t); // 返回 [0,180]
}
double rad(Vector a,Vector b)//角aob弧度大小
{
return fabs(atan2(fabs(a^b),a*b));
}
point rotleft(point a) {return point(-a.y,a.x);}//逆时针旋转90度
point rotright(point a) {return point(a.y,-a.x);}//顺时针旋转90度
point rotate(point a,point o,double angle)//点a绕点p逆时针旋转弧度angle [0,π]
{
point v=a-o;
double c=cos(angle),s=sin(angle);
return point(o.x+v.x*c-v.y*s,o.y+v.x*s+v.y*c);
}
Vector Rotate(Vector a,double angle)//向量旋转弧度angle [0,π]
{
Vector b(sin(angle),cos(angle));
return Vector(a^b,a*b);
}
//1: b在a的逆时针方向
//-1: b在a的顺时针方向
//2: b与a同向共线
//-2: b在a反向共线
int cross(Vector a,Vector b)//向量b与a的方位关系
{
int x=sgn(a^b),y=sgn(a*b);
if(x!=0) return x;
else return 2*y;
}
bool sameline(point a,point b,point c) {return sgn((b-a)^(c-b))==0;}//三点共线
double cross(point a,point b,point c) {return (b-a)^(c-a);}//ab叉乘ac
double dot(point a,point b,point c) {return (b-a)*(c-a);}//ab点乘ac
typedef struct line
{
point s,e;
line(){}
line(point _s,point _e) {s =_s; e= _e;}
line(point p,double angle)//点斜
{
s=p;
if(sgn(angle-pi/2)==0) e=(s+point(0,1));
else e=(s+point(1,tan(angle)));
}
line(double a,double b,double c)//ax+by+c=0;
{
if(sgn(a)==0) {s=point(0,-c/b);e=point(1,-c/b);}
else if(sgn(b)==0) {s=point(-c/a,0);e=point(-c/a,1);}
else {s=point(0,-c/b);e=point(1,(-c-a)/b);}
}
double length() {return s.dis(e);}//线段长度
double angle1()//返回[0,π]的基于x轴的斜倾角(弧度制)
{
double k=atan2(e.y-s.y,e.x-s.x);
if(sgn(k)<0) k+=pi;
if(sgn(k-pi)==0) k-=pi;
return k;
}
double angle2()//返回(-π,π]的基于x正半轴的斜倾角(弧度制)
{
return atan2(e.y-s.y,e.x-s.x);
}
}seg;
//-1: 在右侧(顺时针)
//1: 在左侧(逆时针)
//0: 在直线上
int relation_p_l(point p,line l) {return sgn((p-l.s)^(l.e-l.s));}//点与直线关系
double dis_p_l(point p,line l) {return fabs((p-l.s)^(l.e-l.s))/l.length();}//点到直线的距离
point prog(point p,line l)//点p在直线l上的投影点(垂足)
{
point x=l.e-l.s;
return l.s+((x*(x*(p-l.s)))/(x.len2()));
}
point mirror(point p,line l)//点p在直线l上的对称点
{
point q=prog(p,l);
return point(2*q.x-p.x,2*q.y-p.y);
}
bool relation_p_seg(point p,seg l)//点是否在线段上
{
return sgn((p-l.s)^(l.e-l.s))==0&&sgn((p-l.s)*(p-l.e))<=0;
}
double dis_p_seg(point p,seg l)//点到线段的距离
{
if(sgn((p-l.s)*(l.e-l.s))<0||sgn((p-l.e)*(l.s-l.e))<0)
return min(p.dis(l.s),p.dis(l.e));
return dis_p_l(p,l);
}
bool parallel(line l,line v) {return sgn((l.e-l.s)^(v.e-v.s))==0;}//判断平行
//0: 平行
//1: 共线
//-1: 相交
int relation_l_l(line l,line v)//判断两直线的位置关系
{
if(parallel(l,v)) return relation_p_l(l.s,v)==0;
return -1;
}
//-1: 规范相交
//1: 非规范相交(顶点处相交)
//0: 不相交
int relation_l_seg(line l,seg v)//直线与线段位置关系
{
int d1=sgn((l.e-l.s)^(v.s-l.s));
int d2=sgn((l.e-l.s)^(v.e-l.s));
if((d1^d2)==-2) return -1;
return (d1==0||d2==0);
}
//-1: 规范相交(恰有一个交点且非端点,即互相穿过)
//1: 非规范相交
//0: 不相交
int relation_seg_seg(seg l,seg v)//两线段相交判断
{
int d1=sgn((l.e-l.s)^(v.s-l.s));
int d2=sgn((l.e-l.s)^(v.e-l.s));
int d3=sgn((v.e-v.s)^(l.s-v.s));
int d4=sgn((v.e-v.s)^(l.e-v.s));
if ((d1^d2)==-2&&(d3^d4)==-2) return -1;
return (d1==0&&sgn((v.s-l.s)*(v.s-l.e))<=0)||
(d2==0&&sgn((v.e-l.s)*(v.e-l.e))<=0)||
(d3==0&&sgn((l.s-v.s)*(l.s-v.e))<=0)||
(d4==0&&sgn((l.e-v.s)*(l.e-v.e))<=0);
}
double dis_seg_seg(seg l,seg v)//线段到线段的距离
{
if(relation_seg_seg(l,v)) return 0;
return min(min(dis_p_seg(v.s,l),dis_p_seg(v.e,l)),min(dis_p_seg(l.s,v),dis_p_seg(l.e,v)));
}
bool lcrossl(line a,line b)//求两直线的交点(需要保证直线不平行或共线)
{
point u=a.s-b.s,v=a.e-a.s,w=b.e-b.s;
//***************************
if((w^v)==0)//o2优化出问题的时候直接返回mle,
{
vector<int>q;
while(1) q.push_back(1);
}
//***************************
double t=(u^w)/(w^v);
return sgn(t)>=0;
}
void solve()
{
point a,b;
cin>>a.x>>a.y;
cin>>b.x>>b.y;
point h1,h2,g1,g2;
cin>>h1.x>>h1.y>>h2.x>>h2.y;
cin>>g1.x>>g1.y>>g2.x>>g2.y;
seg now(a,b),h(h1,h2),g(g1,g2);
if(a==b)
{
cout<<0<<endl;
return;
}
if(relation_seg_seg(now,h)==0&&relation_seg_seg(now,g)==0)
{
cout<<0<<endl;
}
else
{
vector<line>A,B;
if(relation_seg_seg(seg(a,h1),g)!=-1) A.push_back(line(a,h1));
if(relation_seg_seg(seg(a,h2),g)!=-1) A.push_back(line(a,h2));
if(relation_seg_seg(seg(a,g1),h)!=-1) A.push_back(line(a,g1));
if(relation_seg_seg(seg(a,g2),h)!=-1) A.push_back(line(a,g2));
if(relation_seg_seg(seg(b,h1),g)!=-1) B.push_back(line(b,h1));
if(relation_seg_seg(seg(b,h2),g)!=-1) B.push_back(line(b,h2));
if(relation_seg_seg(seg(b,g1),h)!=-1) B.push_back(line(b,g1));
if(relation_seg_seg(seg(b,g2),h)!=-1) B.push_back(line(b,g2));
for(auto x:A)
{
for(auto y:B)
{
if(relation_l_l(x,y)==-1)
{
if(lcrossl(x,y))
{
cout<<1<<endl;
return;
}
// Vector u=point(x.e-x.s);
// Vector v=point(z-x.s);
// Vector u1=point(y.e-y.s);
// Vector v1=point(z-y.s);
// if(sgn(u*v)>0&&sgn(u1*v1)>0)
// {
// // debug(x.e.x);
// // debug(x.e.y);
// // debug(x.s.x);
// // debug(x.s.y);
// // debug(y.e.x);
// // debug(y.e.y);
// // debug(y.s.x);
// // debug(y.s.y);
// // debug(z.x);
// // debug(z.y);
// // debug(u.x);
// // debug(u.y);
// // debug(v.x);
// // debug(v.y);
// cout<<1<<endl;
// return;
// }
}
}
}
cout<<2<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
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: -100
Wrong Answer
time: 0ms
memory: 3600kb
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'