Submission #44664

#	Time	Username	Problem	Language	Result	Execution time	Memory
44664		zscoder	Fences (JOI18_fences)	C++17	100 / 100	538 ms	3720 KiB

fences

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

const double eps=1e-8;
const double pi=acos(-1.0);
const double inf=1e20;
const int maxp=111111;
int dblcmp(double d)
{
    if (fabs(d)<eps)return 0;
    return d>eps?1:-1;
}
inline double sqr(double x){return x*x;}
struct point 
{
    double x,y;
    point(){}
    point(double _x,double _y):
    x(_x),y(_y){};
    void input()
    {
        scanf("%lf%lf",&x,&y);
    }
    void output()
    {
        printf("%.2f %.2f\n",x,y);
    }
    bool operator==(point a)const
    {
        return dblcmp(a.x-x)==0&&dblcmp(a.y-y)==0;
    }
    bool operator<(point a)const
    {
        return dblcmp(a.x-x)==0?dblcmp(y-a.y)<0:x<a.x;
    }
    double len()
    {
        return hypot(x,y);
    }
    double len2()
    {
        return x*x+y*y;
    }
    double distance(point p)
    {
        return hypot(x-p.x,y-p.y);
    }
    point add(point p)
    {
        return point(x+p.x,y+p.y);
    }
    point sub(point p)
    {
        return point(x-p.x,y-p.y);
    }
    point mul(double b)
    {
        return point(x*b,y*b);
    }
    point div(double b)
    {
        return point(x/b,y/b);
    }
    double dot(point p)
    {
        return x*p.x+y*p.y;
    }
    double det(point p)
    {
        return x*p.y-y*p.x;
    }
    double rad(point a,point b)
    {
        point p=*this;
        return fabs(atan2(fabs(a.sub(p).det(b.sub(p))),a.sub(p).dot(b.sub(p))));
    }
    point trunc(double r)
    {
        double l=len();
        if (!dblcmp(l))return *this;
        r/=l;
        return point(x*r,y*r);
    }
    point rotleft()
    {
        return point(-y,x);
    }
    point rotright()
    {
        return point(y,-x);
    }
    point rotate(point p,double angle)//绕点p逆时针旋转angle角度 
    {
        point v=this->sub(p);
        double c=cos(angle),s=sin(angle);
        return point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
    }        
};

struct line 
{
    point a,b;
    line(){}
    line(point _a,point _b)
    {
        a=_a;
        b=_b;
    }
    bool operator==(line v)
    {
        return (a==v.a)&&(b==v.b);
    }
    //倾斜角angle 
    line(point p,double angle)
    {
        a=p;
        if (dblcmp(angle-pi/2)==0)
        {
            b=a.add(point(0,1));
        }
        else 
        {
            b=a.add(point(1,tan(angle)));
        }
    }       
    //ax+by+c=0
    line(double _a,double _b,double _c)
    {
        if (dblcmp(_a)==0)
        {
            a=point(0,-_c/_b);
            b=point(1,-_c/_b);
        }
        else if (dblcmp(_b)==0)
        {
            a=point(-_c/_a,0);
            b=point(-_c/_a,1);
        }
        else 
        {
            a=point(0,-_c/_b);
            b=point(1,(-_c-_a)/_b);
        }
    }
    void input()
    {
        a.input();
        b.input();
    }
    void adjust()
    {
        if (b<a)swap(a,b);
    }
    double length()
    {
        return a.distance(b);
    }
    double angle()//直线倾斜角 0<=angle<180 
    {
        double k=atan2(b.y-a.y,b.x-a.x);
        if (dblcmp(k)<0)k+=pi;
        if (dblcmp(k-pi)==0)k-=pi;
        return k;
    }
    //点和线段关系
    //1 在逆时针
    //2 在顺时针
    //3 平行
    int relation(point p)
    {
        int c=dblcmp(p.sub(a).det(b.sub(a)));
        if (c<0)return 1;
        if (c>0)return 2;
        return 3;
    }
    bool pointonseg(point p)
    {
        return dblcmp(p.sub(a).det(b.sub(a)))==0&&dblcmp(p.sub(a).dot(p.sub(b)))<=0;
    }
    bool parallel(line v)
    {
        return dblcmp(b.sub(a).det(v.b.sub(v.a)))==0;
    }
    //2 规范相交
    //1 非规范相交
    //0 不相交 
    int segcrossseg(line v)
    {
        int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
        int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
        int d3=dblcmp(v.b.sub(v.a).det(a.sub(v.a)));
        int d4=dblcmp(v.b.sub(v.a).det(b.sub(v.a)));
        if ((d1^d2)==-2&&(d3^d4)==-2)return 2;
        return (d1==0&&dblcmp(v.a.sub(a).dot(v.a.sub(b)))<=0||
                d2==0&&dblcmp(v.b.sub(a).dot(v.b.sub(b)))<=0||
                d3==0&&dblcmp(a.sub(v.a).dot(a.sub(v.b)))<=0||
                d4==0&&dblcmp(b.sub(v.a).dot(b.sub(v.b)))<=0);        
    }        
    int linecrossseg(line v)//*this seg v line
    {
        int d1=dblcmp(b.sub(a).det(v.a.sub(a)));
        int d2=dblcmp(b.sub(a).det(v.b.sub(a)));
        if ((d1^d2)==-2)return 2;
        return (d1==0||d2==0);
    }
    //0 平行
    //1 重合
    //2 相交 
    int linecrossline(line v)
    {
        if ((*this).parallel(v))
        {
            return v.relation(a)==3;
        }
        return 2;
    }
    point crosspoint(line v)
    {
        double a1=v.b.sub(v.a).det(a.sub(v.a));
        double a2=v.b.sub(v.a).det(b.sub(v.a));
        return point((a.x*a2-b.x*a1)/(a2-a1),(a.y*a2-b.y*a1)/(a2-a1));
    }
    double dispointtoline(point p)
    {
        return fabs(p.sub(a).det(b.sub(a)))/length();
    }
    double dispointtoseg(point p)
    {
        if (dblcmp(p.sub(b).dot(a.sub(b)))<0||dblcmp(p.sub(a).dot(b.sub(a)))<0)
        {
            return min(p.distance(a),p.distance(b));
        }
        return dispointtoline(p);
    }
    point lineprog(point p)
    {
        return a.add(b.sub(a).mul(b.sub(a).dot(p.sub(a))/b.sub(a).len2()));
    }
    point symmetrypoint(point p)
    {
        point q=lineprog(p);
        return point(2*q.x-p.x,2*q.y-p.y);
    }   
};

bool clash(line a, line b)
{
	return (a.segcrossseg(b)!=0);
}

bool clash2(line a, line b)
{
	if(a.segcrossseg(b)!=0)
	{
		if(a.parallel(b)) return false;
		point tmp = a.crosspoint(b);
		////cerr<<"CROSSPOINT : \n"<<a.a.x<<' '<<a.a.y<<' '<<a.b.x<<' '<<a.b.y<<'\n'<<b.a.x<<' '<<b.a.y<<' '<<b.b.x<<' '<<b.b.y<<'\n'<<tmp.x<<' '<<tmp.y<<'\n';
		if(b.a == tmp || b.b == tmp || a.a == tmp || a.b == tmp) return false;
		return true;
	}
	return false;
}

const int N = 422;
point a[N+11];
point b[N+11];
point square[4];
ld dist[N+11][N+11];
line ray;

void amin(ld &x, ld y)
{
	x=min(x,y);
}

void add_edge(int u, int v, ld d, bool intersect)
{
	u*=2; v*=2;
	if(intersect) //if u-v intersects the ray
	{
		for(int i=0;i<2;i++)
		{
			amin(dist[u][v^1],d); amin(dist[u^1][v],d);
			swap(u,v);
		}
	}
	else
	{
		for(int i=0;i<2;i++)
		{
			amin(dist[u][v],d); amin(dist[u^1][v^1],d);
			swap(u,v);
		}
	}
}
int n,s;
bool good(point a, point b)
{
	for(int i=0;i<4;i++)
	{
		if(clash2(line(a,b), line(square[i],square[(i+1)%4]))) return false;
	}
	point tmp = point((a.x+b.x)*0.5, (a.y+b.y)*0.5); //check if the line segment lies within the square
	if(tmp.x>-s&&tmp.x<s&&tmp.y>-s&&tmp.y<s) return false;
	return true;
}

ld getdist(point a, point b)
{
	return a.distance(b);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>s; ld ans = s*8;
	square[0] = point(-s,-s); 
	square[1] = point(-s, s);
	square[2] = point(s,s);
	square[3] = point(s,-s);
	ray = line(point(0,0), point(1,2018));
	for(int i=0;i<n;i++)
	{
		cin>>a[i].x>>a[i].y>>b[i].x>>b[i].y;
	}
	for(int i=0;i<4;i++)
	{
		a[n] = square[i];
		b[n++] = square[i];
	}
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			dist[i][j]=(i==j?0.0:ld(1e12));
		}
	}
	for(int i=0;i<n;i++)
	{
		add_edge(i,i+n,0,clash(ray, line(a[i], b[i])));
		for(int j=i+1;j<n;j++)
		{
			if(good(a[i],a[j])) 
			{
				//cerr<<"DO ZZZ "<<i<<' '<<j<<'\n';
				//cerr<<"LINE : "<<a[i].x<<' '<<a[i].y<<' '<<a[j].x<<' '<<a[j].y<<'\n';
				add_edge(i,j,getdist(a[i],a[j]),clash(ray,line(a[i],a[j])));
			}
			if(good(a[i],b[j])) 
			{
				//cerr<<"DO ZZZ "<<i<<' '<<j+n<<'\n';
				//cerr<<"LINE : "<<a[i].x<<' '<<a[i].y<<' '<<b[j].x<<' '<<b[j].y<<'\n';
				add_edge(i,j+n,getdist(a[i],b[j]),clash(ray,line(a[i],b[j])));
			}
			if(good(b[i],a[j])) 
			{
				//cerr<<"DO ZZZ "<<i+n<<' '<<j<<'\n';
				//cerr<<"LINE : "<<b[i].x<<' '<<b[i].y<<' '<<a[j].x<<' '<<a[j].y<<'\n';
				add_edge(i+n,j,getdist(b[i],a[j]),clash(ray,line(b[i],a[j])));
			}
			if(good(b[i],b[j])) 
			{
				//cerr<<"DO ZZZ "<<i+n<<' '<<j+n<<'\n';
				//cerr<<"LINE : "<<b[i].x<<' '<<b[i].y<<' '<<b[j].x<<' '<<b[j].y<<'\n';
				add_edge(i+n,j+n,getdist(b[i],b[j]),clash(ray,line(b[i],b[j])));
			}
			for(int z=0;z<2;z++)
			{
				point foot = line(a[j], b[j]).lineprog(a[i]);
				if(line(a[j], b[j]).pointonseg(foot) && good(foot, a[i]))
				{
					//cerr<<"DO "<<i<<' '<<j<<' '<<j+n<<'\n';
					add_edge(i, j, getdist(a[i], foot), clash(ray, line(a[i], foot))^clash(ray, line(a[j], foot)));
					add_edge(i, j + n, getdist(a[i], foot), clash(ray, line(a[i], foot))^clash(ray, line(b[j], foot)));
				}
				foot = line(a[j], b[j]).lineprog(b[i]);
				if(line(a[j], b[j]).pointonseg(foot) && good(foot, b[i]))
				{
					//cerr<<"DO "<<i+n<<' '<<j<<' '<<j+n<<'\n';
					add_edge(i + n, j, getdist(b[i], foot), clash(ray, line(b[i], foot))^clash(ray, line(a[j], foot)));
					add_edge(i + n, j + n, getdist(b[i], foot), clash(ray, line(b[i], foot))^clash(ray, line(b[j], foot)));
				}
				swap(i,j);
			}
		}
	}
	for(int i=0;i<4*n;i++)
	{
		for(int j=0;j<4*n;j++)
		{
			//if(dist[i][j]<ld(1e12)) cerr<<"("<<i/2<<","<<i%2<<") ("<<j/2<<","<<j%2<<") "<<dist[i][j]<<'\n';
		}
	}
	for(int k=0;k<4*n;k++)
	{
		for(int i=0;i<4*n;i++)
		{
			for(int j=0;j<4*n;j++)
			{
				amin(dist[i][j],dist[i][k]+dist[k][j]);
			}
		}
	}
	for(int i=0;i<2*n;i++)
	{
		//cerr<<"DIST : "<<i*2<<' '<<i*2+1<<' '<<dist[i*2][i*2+1]<<'\n';
		amin(ans, dist[i*2][i*2+1]);
	}
	cout<<fixed<<setprecision(10)<<ans<<'\n';
}

Compilation message (stderr)

fences.cpp: In member function 'int line::segcrossseg(line)':
fences.cpp:213:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         return (d1==0&&dblcmp(v.a.sub(a).dot(v.a.sub(b)))<=0||
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fences.cpp:215:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 d3==0&&dblcmp(a.sub(v.a).dot(a.sub(v.b)))<=0||
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fences.cpp:216:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                 d4==0&&dblcmp(b.sub(v.a).dot(b.sub(v.b)))<=0);        
                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 33 / 33
• Subtask 3: 49 / 49