[POJ 3336] | Eurce's Blog

计算几何

题意：给出一个起点和终点坐标，以及最多100条线段和3000个黑点，问从起点出发是否能到达终点。移动过程中存在以下限制：只能沿线段移动，如果遇到交点，可以转移到另一条线段上。如果移动过程中遇到黑点：若黑点在交点处，则无法转移到其他线段；否则无法跨越黑点继续沿线段移动。

分析：数据范围很小，可以首先枚举出所有的点，并对每条线段计算出所有在其上的点，排序，对所有相邻可达点连边，最后从起点出发深搜即可。这里的关键在于，处理某条线上的点时，若在相同位置遇到了黑点和白点，那么需要在后续处理中忽略所有该位置上的点。每次仅当两个相邻点都为白点时才连边，这样可以确保仅能通过有效交点转移到其他线段，且不会越过在单一线段上的黑点。

#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define M 20000
#define eps 1e-8

int n,m,hd[M],el,pl,ql,S,E;
double xs,ys,xe,ye;
int stk[M],sl,b[M];

struct O
{
    double x1,y1,x2,y2;
    double a,b,c;
}o[100];

struct P
{
    int b;
    double x,y;
    bool operator < (const P& p) const
    {
        if(x<p.x-eps)
            return 1;
        if(x>p.x+eps)
            return 0;
        if(y<p.y-eps)
            return 1;
        if(y>p.y+eps)
            return 0;
        return b<p.b;
    }
}p[M];

struct Q
{
    int pi;
    double d;
    bool operator < (const Q& p) const
    {
        return d<p.d;
    }
}q[M];

struct E
{
    int v,p;
}e[M*10];

void addp(int b,double x,double y)
{
    p[pl].b=b; p[pl].x=x; p[pl].y=y; pl++;
}

void addq(int pi,double d)
{
    q[ql].pi=pi; q[ql].d=d; ql++;
}

void adde(int u,int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
    e[el].v=u; e[el].p=hd[v]; hd[v]=el++;
}

double crs(double x1,double y1,double x2,double y2)
{
    return x1*y2-x2*y1;
}

bool its(int i,int j)
{
    double x1=o[i].x1,y1=o[i].y1,x2=o[i].x2,y2=o[i].y2;
    double x3=o[j].x1,y3=o[j].y1,x4=o[j].x2,y4=o[j].y2;
    double v;
    v=crs(x3-x1,y3-y1,x2-x1,y2-y1)*crs(x2-x1,y2-y1,x4-x1,y4-y1);
    if(v<-eps)
        return 0;
    v=crs(x1-x3,y1-y3,x4-x3,y4-y3)*crs(x4-x3,y4-y3,x2-x3,y2-y3);
    if(v<-eps)
        return 0;
    return 1;
}

void calc(int i,int j,double &x,double &y)
{
    double a1=o[i].a,b1=o[i].b,c1=o[i].c;
    double a2=o[j].a,b2=o[j].b,c2=o[j].c;
    if(fabs(a1)<eps)
    {
        y=-c1/b1;
        x=-(b2*y+c2)/a2;
    }
    else
    {
        y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
        x=-(b1*y+c1)/a1;
    }
}

bool on(int oi,int pi)
{
    double x1=o[oi].x1,y1=o[oi].y1,x2=o[oi].x2,y2=o[oi].y2;
    double x=p[pi].x,y=p[pi].y;
    double d=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
    double d1=sqrt(pow(x-x1,2)+pow(y-y1,2));
    double d2=sqrt(pow(x-x2,2)+pow(y-y2,2));
    return abs(d-d1-d2)<eps;
}

void init()
{
    int i,j,k,l;
    double x,y;
    el=pl=0;
    memset(hd,-1,sizeof hd);
    scanf("%lf%lf%lf%lf",&xs,&ys,&xe,&ye);
    addp(0,xs,ys);
    addp(0,xe,ye);
    for(i=0;i<n;i++)
    {
        scanf("%lf%lf%lf%lf",&o[i].x1,&o[i].y1,&o[i].x2,&o[i].y2);
        if(fabs(o[i].y1-o[i].y2)<eps)
        {
            o[i].a=0;
            o[i].b=1;
            o[i].c=-o[i].y1;
        }
        else
        {
            o[i].a=1;
            o[i].b=(o[i].x2-o[i].x1)/(o[i].y1-o[i].y2);
            o[i].c=-o[i].x1-o[i].b*o[i].y1;
        }
    }
    for(i=0;i<m;i++)
    {
        scanf("%lf%lf",&x,&y);
        addp(1,x,y);
    }
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(its(i,j))
            {
                calc(i,j,x,y);
                addp(0,x,y);
            }
        }
    }
    sort(p,p+pl);
    for(i=1;i<pl;i++)
    {
        if(fabs(p[i].x-p[i-1].x)<eps&&fabs(p[i].y-p[i-1].y)<eps)
        {
            if(p[i-1].b==2)
            {
                p[i].b=2;
                continue;
            }
            if(p[i-1].b!=p[i].b)
            {
                for(l=i;l>-1;l--)
                {
                    if(fabs(p[i].x-p[l].x)>eps
                            ||fabs(p[i].y-p[l].y)>eps)
                        break;
                    p[l].b=2;
                }
            }
        }
    }
    for(i=0;i<pl;i++)
    {
        if(fabs(p[i].x-xs)<eps&&fabs(p[i].y-ys)<eps)
            S=i;
        if(fabs(p[i].x-xe)<eps&&fabs(p[i].y-ye)<eps)
            E=i;
    }
    for(i=0;i<n;i++)
    {
        ql=0;
        for(l=0;l<pl;l++)
        {
            if(p[l].b!=2&&on(i,l))
                addq(l,(p[l].x-o[i].x1)*(p[l].x-o[i].x1)
                        +(p[l].y-o[i].y1)*(p[l].y-o[i].y1));
        }
        sort(q,q+ql);
        for(l=0;l<ql-1;l++)
        {
            if(p[q[l].pi].b==0&&p[q[l+1].pi].b==0)
                adde(q[l].pi,q[l+1].pi);
        }
    }
}

void solve()
{
    int i,j,k,l;
    if(S==E)
    {
        puts("YES");
        return;
    }
    if(p[S].b==2||p[E].b==2)
    {
        puts("NO");
        return;
    }
    memset(b,0,sizeof b);
    sl=0;
    b[S]=1;
    stk[sl++]=S;
    while(sl&&!b[E])
    {
        i=stk[--sl];
        for(l=hd[i];l!=-1;l=e[l].p)
        {
            j=e[l].v;
            if(b[j])
                continue;
            b[j]=1;
            stk[sl++]=j;
        }
    }
    puts(b[E]?"YES":"NO");
}

int main()
{
    scanf("%*d");
    while(~scanf("%d%d",&n,&m))
    {
        init();
        solve();
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

#include<set>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define M 20000

#define eps 1e-8

int n,m,hd[M],el,pl,ql,S,E;

double xs,ys,xe,ye;

int stk[M],sl,b[M];

struct O

{

double x1,y1,x2,y2;

double a,b,c;

}o[100];

struct P

{

int b;

double x,y;

bool operator < (const P& p) const

{

if(x<p.x-eps)

return 1;

if(x>p.x+eps)

return 0;

if(y<p.y-eps)

return 1;

if(y>p.y+eps)

return 0;

return b<p.b;

}

}p[M];

struct Q

{

int pi;

double d;

bool operator < (const Q& p) const

{

return d<p.d;

}

}q[M];

struct E

{

int v,p;

}e[M*10];

void addp(int b,double x,double y)

{

p[pl].b=b; p[pl].x=x; p[pl].y=y; pl++;

}

void addq(int pi,double d)

{

q[ql].pi=pi; q[ql].d=d; ql++;

}

void adde(int u,int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

e[el].v=u; e[el].p=hd[v]; hd[v]=el++;

}

double crs(double x1,double y1,double x2,double y2)

{

return x1*y2-x2*y1;

}

bool its(int i,int j)

{

double x1=o[i].x1,y1=o[i].y1,x2=o[i].x2,y2=o[i].y2;

double x3=o[j].x1,y3=o[j].y1,x4=o[j].x2,y4=o[j].y2;

double v;

v=crs(x3-x1,y3-y1,x2-x1,y2-y1)*crs(x2-x1,y2-y1,x4-x1,y4-y1);

if(v<-eps)

return 0;

v=crs(x1-x3,y1-y3,x4-x3,y4-y3)*crs(x4-x3,y4-y3,x2-x3,y2-y3);

if(v<-eps)

return 0;

return 1;

}

void calc(int i,int j,double &x,double &y)

{

double a1=o[i].a,b1=o[i].b,c1=o[i].c;

double a2=o[j].a,b2=o[j].b,c2=o[j].c;

if(fabs(a1)<eps)

{

y=-c1/b1;

x=-(b2*y+c2)/a2;

}

else

{

y=(a2*c1-a1*c2)/(a1*b2-a2*b1);

x=-(b1*y+c1)/a1;

}

bool on(int oi,int pi)

{

double x1=o[oi].x1,y1=o[oi].y1,x2=o[oi].x2,y2=o[oi].y2;

double x=p[pi].x,y=p[pi].y;

double d=sqrt(pow(x1-x2,2)+pow(y1-y2,2));

double d1=sqrt(pow(x-x1,2)+pow(y-y1,2));

double d2=sqrt(pow(x-x2,2)+pow(y-y2,2));

return abs(d-d1-d2)<eps;

}

void init()

{

int i,j,k,l;

double x,y;

el=pl=0;

memset(hd,-1,sizeof hd);

scanf("%lf%lf%lf%lf",&xs,&ys,&xe,&ye);

addp(0,xs,ys);

addp(0,xe,ye);

for(i=0;i<n;i++)

{

scanf("%lf%lf%lf%lf",&o[i].x1,&o[i].y1,&o[i].x2,&o[i].y2);

if(fabs(o[i].y1-o[i].y2)<eps)

{

o[i].a=0;

o[i].b=1;

o[i].c=-o[i].y1;

}

else

{

o[i].a=1;

o[i].b=(o[i].x2-o[i].x1)/(o[i].y1-o[i].y2);

o[i].c=-o[i].x1-o[i].b*o[i].y1;

}

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

{

scanf("%lf%lf",&x,&y);

addp(1,x,y);

}

for(i=0;i<n-1;i++)

{

for(j=i+1;j<n;j++)

{

if(its(i,j))

{

calc(i,j,x,y);

addp(0,x,y);

}

sort(p,p+pl);

for(i=1;i<pl;i++)

{

if(fabs(p[i].x-p[i-1].x)<eps&&fabs(p[i].y-p[i-1].y)<eps)

{

if(p[i-1].b==2)

{

p[i].b=2;

continue;

}

if(p[i-1].b!=p[i].b)

{

for(l=i;l>-1;l--)

{

if(fabs(p[i].x-p[l].x)>eps

||fabs(p[i].y-p[l].y)>eps)

break;

p[l].b=2;

}

for(i=0;i<pl;i++)

{

if(fabs(p[i].x-xs)<eps&&fabs(p[i].y-ys)<eps)

S=i;

if(fabs(p[i].x-xe)<eps&&fabs(p[i].y-ye)<eps)

E=i;

}

for(i=0;i<n;i++)

{

ql=0;

for(l=0;l<pl;l++)

{

if(p[l].b!=2&&on(i,l))

addq(l,(p[l].x-o[i].x1)*(p[l].x-o[i].x1)

+(p[l].y-o[i].y1)*(p[l].y-o[i].y1));

}

sort(q,q+ql);

for(l=0;l<ql-1;l++)

{

if(p[q[l].pi].b==0&&p[q[l+1].pi].b==0)

adde(q[l].pi,q[l+1].pi);

}

void solve()

{

int i,j,k,l;

if(S==E)

{

puts("YES");

return;

}

if(p[S].b==2||p[E].b==2)

{

puts("NO");

return;

}

memset(b,0,sizeof b);

sl=0;

b[S]=1;

stk[sl++]=S;

while(sl&&!b[E])

{

i=stk[--sl];

for(l=hd[i];l!=-1;l=e[l].p)

{

j=e[l].v;

if(b[j])

continue;

b[j]=1;

stk[sl++]=j;

}

puts(b[E]?"YES":"NO");

}

int main()

{

scanf("%*d");

while(~scanf("%d%d",&n,&m))

{

init();

solve();

}

return 0;

}