ZOJ 3495 Lego Bricks

计算几何，暴力。

题目中有一句话：$The$ $mass$ $of$ $each$ $brick$ $is$ $equally$ $distributed$ $and$ $it$ $will$ $be$ $stable$ $if$ $it$ $is$ $placed$ $on$ $bases$ $or$ $stable$ $bricks$ $and$ $the$ $moment$ $of$ $it$ $can$ $be$ $zero$ $when$ $it$ $is$ $placed$.

核心原则：左右半段均有稳定的东西支撑，这条才算是稳定的。暴力扩展就可以了。需要用到判断线段不严格相交以及点到线段的最小距离。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<ctime>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0);

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

template <class T>

inline void read(T &x)

{

    char c = getchar();

    x = ;

    while(!isdigit(c)) c = getchar();

    while(isdigit(c))

    {

        x = x *  + c - '';

        c = getchar();

    }

}

const double eps=1e-;

#define zero(x)(((x)>0?(x):(-x))<eps)

struct point

{

    double x,y;

    point(double X,double Y)

    {

        x=X;

        y=Y;

    }

};

double xmult(point p1,point p2,point p0)

{

    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);

}

int dots_inline(point p1,point p2,point p3)

{

    return zero(xmult(p1,p2,p3));

}

int same_side(point p1,point p2,point l1,point l2)

{

    return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;

}

int dot_online_in(point p,point l1,point l2)

{

    return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;

}

int intersect_in(point u1,point u2,point v1,point v2)

{

    if(!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2)) return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);

    return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);

}

int T;

struct YUAN

{

    double x,y,r;

} yuan[];

struct XIAN

{

    double p1x,p1y,p2x,p2y;

} xian[];

int n,m;

int f[];

double DIS(point a,point b)

{

    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

point intersection(point u1,point u2,point v1,point v2)

{

    point ret=u1;

    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))

             /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));

    ret.x+=(u2.x-u1.x)*t;

    ret.y+=(u2.y-u1.y)*t;

    return ret;

}

point ptoseg(point p,point l1,point l2)

{

    point t=p;

    t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;

    if(xmult(l1,t,p)*xmult(l2,t,p)>eps)

        return DIS(p,l1)<DIS(p,l2)?l1:l2;

    return intersection(p,t,l1,l2);

}

int check(point A,point B,int b)

{

    point F=ptoseg(point(yuan[b].x,yuan[b].y),A,B);

    double dis=DIS(F,point(yuan[b].x,yuan[b].y));

    if(dis<=yuan[b].r) return ;

    return ;

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(int i=; i<=n; i++) scanf("%lf%lf%lf",&yuan[i].x,&yuan[i].y,&yuan[i].r);

        for(int i=; i<=m; i++) scanf("%lf%lf%lf%lf",&xian[i].p1x,&xian[i].p1y,&xian[i].p2x,&xian[i].p2y);

        memset(f,,sizeof f);

        int sum=;

        while()

        {

            int Z=;

            for(int i=; i<=m; i++)

            {

                if(f[i]==) continue;

                point p1= point(xian[i].p1x,xian[i].p1y);

                point p2= point(xian[i].p2x,xian[i].p2y);

                point p3= point((p1.x+p2.x)/,(p1.y+p2.y)/);

                int f1=,f2=;

                for(int j=; j<=n; j++)

                {

                    if(check(p1,p3,j)) f1=;

                    if(check(p2,p3,j)) f2=;

                }

                for(int j=; j<=m; j++)

                {

                    if(f[j]==) continue;

                    if(intersect_in(p1,p3,point(xian[j].p1x,xian[j].p1y),point(xian[j].p2x,xian[j].p2y))) f1=;

                    if(intersect_in(p2,p3,point(xian[j].p1x,xian[j].p1y),point(xian[j].p2x,xian[j].p2y))) f2=;

                }

                if(f1==&&f2==) f[i]=,Z++;

            }

            if(Z==) break;

            sum=sum+Z;

        }

        if(sum!=m) printf("NO\n");

        else printf("YES\n");

    }

    return ;

}

巴特西

ZOJ 3495 Lego Bricks

最新文章

热门文章