月度归档：2014年04月

[POJ 1379]

模拟退火

题意：在最大10000*10000平面的上有最多1000个洞，求平面上的某个点，使得其离所有洞的最近距离最大化。输出精度为小数点后1位。

分析：按照模拟退火的思想，在平面上随机取10个点，将单次移动的步长设为算法中的温度，移动方向随机。初始温度设为矩形对角线长的一半，每轮迭代后温度降为之前的0.8。每轮迭代时，对于每个点，按照当前步长尝试移动50次，如果目标点更优则更新位置，否则维持原位。当温度降低到0.001以下时，终止算法，并取10个点中的最优值输出。

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

#define eps 1e-3
#define its 50
#define pl 10
#define pi 3.141592653589793

int n;
double r,c,x[1000],y[1000];
double xp[pl],yp[pl],dp[pl];

double calc(double xv,double yv)
{
    int i;
    double d=1e30;
    for(i=0;i<n;i++)
        d=min(d,pow(x[i]-xv,2)+pow(y[i]-yv,2));
    return d;
}

bool chk(double xu,double yu)
{
    return xu>0&&xu<r&&yu>0&&yu<c;
}

void init()
{
    int i;
    for(i=0;i<n;i++)
        scanf("%lf%lf",x+i,y+i);
    for(i=0;i<pl;i++)
    {
        xp[i]=r*0.001*(rand()%1000);
        yp[i]=c*0.001*(rand()%1000);
        dp[i]=calc(xp[i],yp[i]);
    }
}

void solve()
{
    int i,j,k,l;
    double a,g,xv,yv,vd,xu,yu,ud;
    srand(time(0));
    for(l=0;l<pl;l++)
    {
        xv=xp[l];
        yv=yp[l];
        vd=dp[l];
        for(g=sqrt(r*r+c*c)*0.5;g>eps;g*=0.8)
        {
            for(i=0;i<its;i++)
            {
                a=2*pi*0.001*(rand()%1000);
                xu=xv+g*cos(a);
                yu=yv+g*sin(a);
                if(!chk(xu,yu))
                    continue;
                ud=calc(xu,yu);
                if(ud>vd)
                {
                    xv=xu;
                    yv=yu;
                    vd=ud;
                }
            }
        }
        xp[l]=xv;
        yp[l]=yv;
        dp[l]=vd;
    }
    for(l=0,ud=0;l<pl;l++)
    {
        if(dp[l]>ud)
        {
            ud=dp[l];
            xv=xp[l];
            yv=yp[l];
        }
    }
    printf("The safest point is (%.1f, %.1f).\n",xv,yv);
}

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

#include<ctime>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-3

#define its 50

#define pl 10

#define pi 3.141592653589793

int n;

double r,c,x[1000],y[1000];

double xp[pl],yp[pl],dp[pl];

double calc(double xv,double yv)

{

int i;

double d=1e30;

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

d=min(d,pow(x[i]-xv,2)+pow(y[i]-yv,2));

return d;

}

bool chk(double xu,double yu)

{

return xu>0&&xu<r&&yu>0&&yu<c;

}

void init()

{

int i;

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

scanf("%lf%lf",x+i,y+i);

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

{

xp[i]=r*0.001*(rand()%1000);

yp[i]=c*0.001*(rand()%1000);

dp[i]=calc(xp[i],yp[i]);

}

void solve()

{

int i,j,k,l;

double a,g,xv,yv,vd,xu,yu,ud;

srand(time(0));

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

{

xv=xp[l];

yv=yp[l];

vd=dp[l];

for(g=sqrt(r*r+c*c)*0.5;g>eps;g*=0.8)

{

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

{

a=2*pi*0.001*(rand()%1000);

xu=xv+g*cos(a);

yu=yv+g*sin(a);

if(!chk(xu,yu))

continue;

ud=calc(xu,yu);

if(ud>vd)

{

xv=xu;

yv=yu;

vd=ud;

}

xp[l]=xv;

yp[l]=yv;

dp[l]=vd;

}

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

{

if(dp[l]>ud)

{

ud=dp[l];

xv=xp[l];

yv=yp[l];

}

printf("The safest point is (%.1f, %.1f).\n",xv,yv);

}

int main()

{

scanf("%*d");

while(~scanf("%lf%lf%d",&r,&c,&n))

{

init();

solve();

}

return 0;

}

ps：非常山寨的实现方式，没有考虑目标位置并非更优时仍进行移动的方案。本题的数据也是很松，只要控制好初始点数，温度下降幅度以及迭代次数，时限范围内很易求得最优位置。

[POJ 1263]

发表回复

Reflections

计算几何

题意：给出二维平面上一个起始点和光线方向，以及平面上最多25个反射球面，问光线每次反射时击中的球编号。当不再击中球面或是反射了超过10次后终止计算。题目保证起始点不在球内，且不会沿切线方向击中球。

分析：由于数据量不大，可以每次计算出光线方向上与每个球的交点，按距离排序后取最近的一个点，根据入射角和切点算出反射角。迭代以上过程10次即可。

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

#define eps 1e-8

int t,n,pl;
double x,y,xd,yd,a,b,c;

struct S
{
    double x,y,r;
}s[25];

struct P
{
    int si;
    double d,x,y;
    bool operator < (const P& p) const
    {
        return d<p.d;
    }
}p[50];

void init()
{
    int i,j,k,l;
    for(i=0;i<n;i++)
        scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].r);
    scanf("%lf%lf%lf%lf",&x,&y,&xd,&yd);
}

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

void calcp(int si)
{
    double x0=s[si].x,y0=s[si].y,r=s[si].r,x1,y1,x2,y2,d;
    double a0,b0,c0;
    if(fabs(a)<eps)
    {
        y1=y2=-c;
        x1=x0+sqrt(r*r-pow(c+y0,2));
        x2=x0-sqrt(r*r-pow(c+y0,2));
    }
    else
    {
        a0=(b*b)/(a*a)+1;
        b0=2*(b*(c+a*x0)/(a*a)-y0);
        c0=pow(c+a*x0,2)/(a*a)+y0*y0-r*r;
        y1=(-b0+sqrt(b0*b0-4*a0*c0))/(2*a0);
        x1=-(b*y1+c)/a;
        y2=(-b0-sqrt(b0*b0-4*a0*c0))/(2*a0);
        x2=-(b*y2+c)/a;
    }
    if(fabs(xd)>eps)
    {
        if((x1-x)/xd>eps)
        {
            d=sqrt(pow(x1-x,2)+pow(y1-y,2));
            addp(si,d,x1,y1);
        }
        if((x2-x)/xd>eps)
        {
            d=sqrt(pow(x2-x,2)+pow(y2-y,2));
            addp(si,d,x2,y2);
        }
    }
    else
    {
        if((y1-y)/yd>eps)
        {
            d=sqrt(pow(x1-x,2)+pow(y1-y,2));
            addp(si,d,x1,y1);
        }
        if((y2-y)/yd>eps)
        {
            d=sqrt(pow(x2-x,2)+pow(y2-y,2));
            addp(si,d,x2,y2);
        }
    }
}

void xng()
{
    double xs,ys,ad,as;
    xd=-xd;
    yd=-yd;
    ad=atan2(yd,xd);
    x=p[0].x;
    y=p[0].y;
    xs=x-s[p[0].si].x;
    ys=y-s[p[0].si].y;
    as=atan2(ys,xs);
    ad=as-(ad-as);
    xd=cos(ad);
    yd=sin(ad);
}

void solve()
{
    int i,j,k,l;
    printf("Scene %d\n",++t);
    for(l=0;l<11;l++)
    {
        if(l)
            printf(" ");
        if(fabs(yd)<eps)
        {
            a=0;
            b=1;
            c=-y;
        }
        else
        {
            a=1;
            b=-xd/yd;
            c=-x-b*y;
        }
        pl=0;
        for(i=0;i<n;i++)
        {
            if(fabs(a*s[i].x+b*s[i].y+c)/sqrt(a*a+b*b)<s[i].r-eps)
                calcp(i);
        }
        if(!pl)
        {
            puts("inf");
            break;
        }
        else if(l==10)
        {
            puts("...");
            break;
        }
        sort(p,p+pl);
        printf("%d",p[0].si+1);
        xng();
    }
    puts("");
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        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

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

int t,n,pl;

double x,y,xd,yd,a,b,c;

struct S

{

double x,y,r;

}s[25];

struct P

{

int si;

double d,x,y;

bool operator < (const P& p) const

{

return d<p.d;

}

}p[50];

void init()

{

int i,j,k,l;

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

scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].r);

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

}

void addp(int si,double d,double x,double y)

{

p[pl].si=si; p[pl].d=d; p[pl].x=x; p[pl].y=y; pl++;

}

void calcp(int si)

{

double x0=s[si].x,y0=s[si].y,r=s[si].r,x1,y1,x2,y2,d;

double a0,b0,c0;

if(fabs(a)<eps)

{

y1=y2=-c;

x1=x0+sqrt(r*r-pow(c+y0,2));

x2=x0-sqrt(r*r-pow(c+y0,2));

}

else

{

a0=(b*b)/(a*a)+1;

b0=2*(b*(c+a*x0)/(a*a)-y0);

c0=pow(c+a*x0,2)/(a*a)+y0*y0-r*r;

y1=(-b0+sqrt(b0*b0-4*a0*c0))/(2*a0);

x1=-(b*y1+c)/a;

y2=(-b0-sqrt(b0*b0-4*a0*c0))/(2*a0);

x2=-(b*y2+c)/a;

}

if(fabs(xd)>eps)

{

if((x1-x)/xd>eps)

{

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

addp(si,d,x1,y1);

}

if((x2-x)/xd>eps)

{

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

addp(si,d,x2,y2);

}

else

{

if((y1-y)/yd>eps)

{

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

addp(si,d,x1,y1);

}

if((y2-y)/yd>eps)

{

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

addp(si,d,x2,y2);

}

void xng()

{

double xs,ys,ad,as;

xd=-xd;

yd=-yd;

ad=atan2(yd,xd);

x=p[0].x;

y=p[0].y;

xs=x-s[p[0].si].x;

ys=y-s[p[0].si].y;

as=atan2(ys,xs);

ad=as-(ad-as);

xd=cos(ad);

yd=sin(ad);

}

void solve()

{

int i,j,k,l;

printf("Scene %d\n",++t);

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

{

if(l)

printf(" ");

if(fabs(yd)<eps)

{

a=0;

b=1;

c=-y;

}

else

{

a=1;

b=-xd/yd;

c=-x-b*y;

}

pl=0;

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

{

if(fabs(a*s[i].x+b*s[i].y+c)/sqrt(a*a+b*b)<s[i].r-eps)

calcp(i);

}

if(!pl)

{

puts("inf");

break;

}

else if(l==10)

{

puts("...");

break;

}

sort(p,p+pl);

printf("%d",p[0].si+1);

xng();

}

puts("");

}

int main()

{

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

{

init();

solve();

}

return 0;

}

ps：分类表最后一题了。还差得远，继续努力。

[POJ 3336]

发表回复

ACM Underground

计算几何

题意：给出一个起点和终点坐标，以及最多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;

}

[POJ 2975] & [POJ 2960]

发表回复

Nim

博弈

题意：Nim问题的必胜策略为，取当前各堆石子数的异或和，若为0则为必败局面；否则取走部分石子使得异或和变为0，便可使对方陷入必败局面。问题为，给出一个局面，问有多少种不同的必胜策略。

分析：很简单，既然必胜策略已知，那么可以算出需要改变那些位才能转化为必败局面。由于，每次只允许改变一堆石子的数目，目标石子数小于等于当前石子数时对应一种必胜策略。最后算一算有多少个堆满足该条件即可。

#include<cstdio>

int n,a[1000],ans;

void solve()
{
    int i,j;
    ans=0;
    for(i=j=0;i<n;i++)
    {
        scanf("%d",a+i);
        j^=a[i];
    }
    if(!j)
    {
        puts("0");
        return;
    }
    for(i=0;i<n;i++)
    {
        if((a[i]^j)<=a[i])
            ans++;
    }
    printf("%d\n",ans);
}

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

#include<cstdio>

int n,a[1000],ans;

void solve()

{

int i,j;

ans=0;

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

{

scanf("%d",a+i);

j^=a[i];

}

if(!j)

{

puts("0");

return;

}

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

{

if((a[i]^j)<=a[i])

ans++;

}

printf("%d\n",ans);

}

int main()

{

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

solve();

return 0;

}

稍微增加难度的话，就是下面这题：

S-Nim

博弈

题意：对于基本的Nim问题，增加如下限制：每次取走的石子数必须在集合S中，若剩余石子不足则可以全部取走。问题是，对于某局面，是否存在必胜策略。

分析：对于给定的S集，考虑将剩余石子的数目划分类别。具体来说，将剩余为0或无法一步到达第0类的石子数设为第0类，可以一步到达第0类（但无法到达第1类）的设为第1类，并依次类推：可以一步到达第0…i-1类且无法到达第i类的设为第i类。这样分类之后，便可以将第i类堆与原Nim问题中的堆石子数为i对应起来。其依据在于，第i类总是能一步到达更低的类别，但无法保持当前状态（或者到达更高类别时会在下一步（由对手操作）回到该类）。由此，便可以对当前各堆的类别数取异或和，并按照结果是否为0来判定是否为必败局面。

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

int n,m,a[100],b[10001],c[10001];

void init()
{
    int i,j,k,l;
    for(i=0;i<n;i++)
        scanf("%d",a+i);
    sort(a,a+n);
    b[0]=0;
    for(i=1;i<10001;i++)
    {
        memset(c,0,sizeof c);
        for(l=0;l<n&&i>=a[l];l++)
            c[b[i-a[l]]]++;
        for(l=0;c[l];l++);
        b[i]=l;
    }
}

void solve()
{
    int i,j,k,l;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d",&l);
        j=0;
        while(l--)
        {
            scanf("%d",&i);
            j^=b[i];
        }
        printf("%c",j?'W':'L');
    }
    puts("");
}

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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,a[100],b[10001],c[10001];

void init()

{

int i,j,k,l;

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

scanf("%d",a+i);

sort(a,a+n);

b[0]=0;

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

{

memset(c,0,sizeof c);

for(l=0;l<n&&i>=a[l];l++)

c[b[i-a[l]]]++;

for(l=0;c[l];l++);

b[i]=l;

}

void solve()

{

int i,j,k,l;

scanf("%d",&m);

while(m--)

{

scanf("%d",&l);

j=0;

while(l--)

{

scanf("%d",&i);

j^=b[i];

}

printf("%c",j?'W':'L');

}

puts("");

}

int main()

{

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

{

init();

solve();

}

return 0;

}

[POJ 1478]

发表回复

Island of Logic

枚举

题意：有一个岛上有3种（仅从外观无法分辨的）生物：神（只说真话）、人（白天说真话，晚上说谎话）、鬼（只说谎话）。给你一段长为n的聊天记录，要求尽量推断出更多的事实。聊天记录中最多涉及5个生物。

分析：事实分为两种，（1）生物的种族、（2）当前时间。基本思路是，可以枚举出所有的事实组合，并根据聊天记录来判断可行性。如果可行，则记录该事实组合。记录时，对于各个生物以及时间分别使用一个位相量，以逻辑或的形式记录其所有可能的取值。最后，仅存在唯一可能取值的位相量即为“事实”。

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

int t,n,ti,r[5],rl,rv[5],tag;
int at,ar[5];
char s[100],ri[128],rc[5];

struct E
{
    int tp;
    int u,v,w;
}e[50];

void init()
{
    int i,j,k,l;
    rl=0;
    tag=0;
    at=0;
    memset(ri,-1,sizeof ri);
    memset(ar,0,sizeof ar);
    for(i=0;i<n;i++)
    {
        scanf("%s",s);
        if(ri[s[0]]==-1)
        {
            ri[s[0]]=rl;
            rc[rl]=s[0];
            rl++;
        }
        j=ri[s[0]];
        e[i].u=j;
        scanf("%s",s);
        if(!strcmp(s,"It"))
        {
            e[i].tp=2;
            scanf("%*s%s",s);
            if(s[0]=='d')
                e[i].w=1;
            else
                e[i].w=2;
        }
        else
        {
            if(s[0]=='I')
                k=j;
            else
            {
                if(ri[s[0]]==-1)
                {
                    ri[s[0]]=rl;
                    rc[rl]=s[0];
                    rl++;
                }
                k=ri[s[0]];
            }
            e[i].v=k;
            scanf("%*s%s",s);
            if(s[0]=='n')
            {
                l=1;
                scanf("%s",s);
            }
            else
                l=0;
            if(s[0]=='l')
            {
                e[i].tp=1;
                e[i].w=2-l;
            }
            else
            {
                e[i].tp=0;
                if(s[0]=='d')
                    e[i].w=1;
                else if(s[0]=='h')
                    e[i].w=2;
                else if(s[0]=='e')
                    e[i].w=4;
                if(l)
                    e[i].w^=7;
            }
        }
    }
}

void mkv()
{
    int i;
    for(i=0;i<rl;i++)
    {
        if(r[i]==1)
        {
            rv[i]=1;
        }
        else if(r[i]==2)
        {
            if(ti==1)
                rv[i]=1;
            else
                rv[i]=2;
        }
        else if(r[i]==4)
        {
            rv[i]=2;
        }
    }
}

bool chk()
{
    int i;
    for(i=0;i<n;i++)
    {
        if(e[i].tp==0)
        {
            if(rv[e[i].u]==1)
            {
                if((r[e[i].v]&e[i].w)==0)
                    return 0;
            }
            else
            {
                if(r[e[i].v]&e[i].w)
                    return 0;
            }
        }
        else if(e[i].tp==1)
        {
            if(rv[e[i].u]==1)
            {
                if((rv[e[i].v]&e[i].w)==0)
                    return 0;
            }
            else
            {
                if(rv[e[i].v]&e[i].w)
                    return 0;
            }
        }
        else if(e[i].tp==2)
        {
            if(rv[e[i].u]==1)
            {
                if((ti&e[i].w)==0)
                    return 0;
            }
            else
            {
                if(ti&e[i].w)
                    return 0;
            }
        }
    }
    return 1;
}

void dfs(int i)
{
    if(i==rl)
    {
        ti=1;
        mkv();
        if(chk())
        {
            for(i=0;i<rl;i++)
                ar[i]|=r[i];
            at|=ti;
        }
        ti=2;
        mkv();
        if(chk())
        {
            for(i=0;i<rl;i++)
                ar[i]|=r[i];
            at|=ti;
        }
        return;
    }
    r[i]=1;
    dfs(i+1);
    r[i]=2;
    dfs(i+1);
    r[i]=4;
    dfs(i+1);
}

void solve()
{
    int i,j,k,l;
    dfs(0);
    for(i=0;i<rl;i++)
    {
        if(ar[i])
        {
            for(j=ar[i],k=0;j;j-=j&-j,k++);
            if(k>1)
                tag=max(tag,1);
            else
                tag=max(tag,2);
        }
    }
    if(at==3)
        tag=max(tag,1);
    else if(at)
        tag=max(tag,2);
    printf("Conversation #%d\n",++t);
    if(!tag)
        puts("This is impossible.\n");
    else if(tag==1)
        puts("No facts are deducible.\n");
    else
    {
        for(i='A';i<'F';i++)
        {
            if(ri[i]==-1)
                continue;
            j=ri[i];
            if(ar[j]==1)
                printf("%c is divine.\n",rc[j]);
            else if(ar[j]==2)
                printf("%c is human.\n",rc[j]);
            else if(ar[j]==4)
                printf("%c is evil.\n",rc[j]);
        }
        if(at==1)
            puts("It is day.");
        else if(at==2)
            puts("It is night.");
        puts("");
    }
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        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<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int t,n,ti,r[5],rl,rv[5],tag;

int at,ar[5];

char s[100],ri[128],rc[5];

struct E

{

int tp;

int u,v,w;

}e[50];

void init()

{

int i,j,k,l;

rl=0;

tag=0;

at=0;

memset(ri,-1,sizeof ri);

memset(ar,0,sizeof ar);

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

{

scanf("%s",s);

if(ri[s[0]]==-1)

{

ri[s[0]]=rl;

rc[rl]=s[0];

rl++;

}

j=ri[s[0]];

e[i].u=j;

scanf("%s",s);

if(!strcmp(s,"It"))

{

e[i].tp=2;

scanf("%*s%s",s);

if(s[0]=='d')

e[i].w=1;

else

e[i].w=2;

}

else

{

if(s[0]=='I')

k=j;

else

{

if(ri[s[0]]==-1)

{

ri[s[0]]=rl;

rc[rl]=s[0];

rl++;

}

k=ri[s[0]];

}

e[i].v=k;

scanf("%*s%s",s);

if(s[0]=='n')

{

l=1;

scanf("%s",s);

}

else

l=0;

if(s[0]=='l')

{

e[i].tp=1;

e[i].w=2-l;

}

else

{

e[i].tp=0;

if(s[0]=='d')

e[i].w=1;

else if(s[0]=='h')

e[i].w=2;

else if(s[0]=='e')

e[i].w=4;

if(l)

e[i].w^=7;

}

void mkv()

{

int i;

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

{

if(r[i]==1)

{

rv[i]=1;

}

else if(r[i]==2)

{

if(ti==1)

rv[i]=1;

else

rv[i]=2;

}

else if(r[i]==4)

{

rv[i]=2;

}

bool chk()

{

int i;

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

{

if(e[i].tp==0)

{

if(rv[e[i].u]==1)

{

if((r[e[i].v]&e[i].w)==0)

return 0;

}

else

{

if(r[e[i].v]&e[i].w)

return 0;

}

else if(e[i].tp==1)

{

if(rv[e[i].u]==1)

{

if((rv[e[i].v]&e[i].w)==0)

return 0;

}

else

{

if(rv[e[i].v]&e[i].w)

return 0;

}

else if(e[i].tp==2)

{

if(rv[e[i].u]==1)

{

if((ti&e[i].w)==0)

return 0;

}

else

{

if(ti&e[i].w)

return 0;

}

return 1;

}

void dfs(int i)

{

if(i==rl)

{

ti=1;

mkv();

if(chk())

{

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

ar[i]|=r[i];

at|=ti;

}

ti=2;

mkv();

if(chk())

{

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

ar[i]|=r[i];

at|=ti;

}

return;

}

r[i]=1;

dfs(i+1);

r[i]=2;

dfs(i+1);

r[i]=4;

dfs(i+1);

}

void solve()

{

int i,j,k,l;

dfs(0);

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

{

if(ar[i])

{

for(j=ar[i],k=0;j;j-=j&-j,k++);

if(k>1)

tag=max(tag,1);

else

tag=max(tag,2);

}

if(at==3)

tag=max(tag,1);

else if(at)

tag=max(tag,2);

printf("Conversation #%d\n",++t);

if(!tag)

puts("This is impossible.\n");

else if(tag==1)

puts("No facts are deducible.\n");

else

{

for(i='A';i<'F';i++)

{

if(ri[i]==-1)

continue;

j=ri[i];

if(ar[j]==1)

printf("%c is divine.\n",rc[j]);

else if(ar[j]==2)

printf("%c is human.\n",rc[j]);

else if(ar[j]==4)

printf("%c is evil.\n",rc[j]);

}

if(at==1)

puts("It is day.");

else if(at==2)

puts("It is night.");

puts("");

}

int main()

{

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

{

init();

solve();

}

return 0;

}

ps：350题了。每做一题在poj上排名都会略微提升，有种在尸体堆里穿行的感觉。（前辈们失敬了）

[POJ 2079]

发表回复

Triangle

旋转卡壳

题意：给出最多50000个点，可取任意3点作三角形，求这些三角形中得面积最大值。

首先，可以明确的是三角形的三个顶点必定在凸包上。求出凸包后，点的数量减少到O(n^2)算法可解。

然后，需要考虑的是最大面积三角形的三点会以何种形式出现。一开始考虑的是对于所有的对踵边，枚举其对应的所有三角形，但是WA。后来发现，三角形的三边可以都不为对踵边。应该枚举的是各个点对应的最大三角形面积。在求顶点i对应的最大三角形面积时，要依次求出当j取其余n-1个点时对应的最大三角形面积，因此，可以构造如下算法：

0. 初始化顶点i为第一个顶点：
1. 初始化j为i在凸包上的下一个顶点
2. 取k为使area(i,j,k)最大的顶点，更新最大面积
3. 当j!=i时，取j为下一个顶点，回到2.；否则取i为下一个顶点，若未取尽，回到1.

其中第3步计算k时，容易利用旋转卡壳的思想证明如下结论：边(i,j+1)对应的k，必定在边(i,j)对应的k之后。由此，对于某个i，其对应的j和k的总自增次数都是O(n)级别的，总体复杂度便是O(n^2)。

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

#define eps 1e-8
#define nt(i) (i==n?0:i)

int n;
int stk[50000],sl;
double mx;

struct E
{
    double x,y,a,r;
    bool operator < (const E &p) const
    {
        return a<p.a;
    }
}e[50001];

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

double area(int i,int j,int k)
{
    double x1=e[i].x,y1=e[i].y;
    double x2=e[j].x,y2=e[j].y;
    double x3=e[k].x,y3=e[k].y;
    return abs(crs(x2-x1,y2-y1,x3-x1,y3-y1))/2;
}

void init()
{
    int i,j,k,l;
    sl=0;
    mx=0;
    double xm=0,ym=0;
    double x1,y1,x2,y2,x3,y3;
    for(i=0;i<n;i++)
    {
        scanf("%lf%lf",&e[i].x,&e[i].y);
        xm+=e[i].x;
        ym+=e[i].y;
    }
    xm/=n;
    ym/=n;
    for(i=0;i<n;i++)
    {
        e[i].x-=xm;
        e[i].y-=ym;
        e[i].a=atan2(e[i].y,e[i].x);
        e[i].r=sqrt(pow(e[i].y,2)+pow(e[i].x,2));
    }
    sort(e,e+n);
    for(i=j=0;i<n;i++)
    {
        if(e[i].r>e[j].r)
            j=i;
    }
    reverse(e,e+j);
    reverse(e+j,e+n);
    reverse(e,e+n);
    e[n++]=e[0];
    stk[sl++]=0;
    stk[sl++]=1;
    for(i=2;i<n;i++)
    {
        if(sl<2)
        {
            stk[sl++]=i;
            continue;
        }
        x1=e[i].x; y1=e[i].y;
        while(sl>1)
        {
            j=stk[sl-1];
            k=stk[sl-2];
            x2=e[j].x; y2=e[j].y;
            x3=e[k].x; y3=e[k].y;
            if(crs(x2-x3,y2-y3,x1-x2,y1-y2)>eps)
                break;
            sl--;
        }
        stk[sl++]=i;
    }
    for(i=0;i<sl-1;i++)
        e[i]=e[stk[i]];
    n=sl-1;
}

void solve()
{
    int i,j,k;
    double u,v;
    for(i=0;i<n;i++)
    {
        for(j=nt(i+1),k=nt(j+1);j!=i;j=nt(j+1))
        {
            u=area(i,j,k);
            while(k!=i&&u<(v=area(i,j,nt(k+1))))
            {
                k=nt(k+1);
                u=v;
            }
            mx=max(mx,u);
        }
    }
    printf("%.2f\n",mx);
}

int main()
{
    while(~scanf("%d",&n)&&~n)
    {
        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

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

#define nt(i) (i==n?0:i)

int n;

int stk[50000],sl;

double mx;

struct E

{

double x,y,a,r;

bool operator < (const E &p) const

{

return a<p.a;

}

}e[50001];

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

{

return x1*y2-x2*y1;

}

double area(int i,int j,int k)

{

double x1=e[i].x,y1=e[i].y;

double x2=e[j].x,y2=e[j].y;

double x3=e[k].x,y3=e[k].y;

return abs(crs(x2-x1,y2-y1,x3-x1,y3-y1))/2;

}

void init()

{

int i,j,k,l;

sl=0;

mx=0;

double xm=0,ym=0;

double x1,y1,x2,y2,x3,y3;

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

{

scanf("%lf%lf",&e[i].x,&e[i].y);

xm+=e[i].x;

ym+=e[i].y;

}

xm/=n;

ym/=n;

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

{

e[i].x-=xm;

e[i].y-=ym;

e[i].a=atan2(e[i].y,e[i].x);

e[i].r=sqrt(pow(e[i].y,2)+pow(e[i].x,2));

}

sort(e,e+n);

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

{

if(e[i].r>e[j].r)

j=i;

}

reverse(e,e+j);

reverse(e+j,e+n);

reverse(e,e+n);

e[n++]=e[0];

stk[sl++]=0;

stk[sl++]=1;

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

{

if(sl<2)

{

stk[sl++]=i;

continue;

}

x1=e[i].x; y1=e[i].y;

while(sl>1)

{

j=stk[sl-1];

k=stk[sl-2];

x2=e[j].x; y2=e[j].y;

x3=e[k].x; y3=e[k].y;

if(crs(x2-x3,y2-y3,x1-x2,y1-y2)>eps)

break;

sl--;

}

stk[sl++]=i;

}

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

e[i]=e[stk[i]];

n=sl-1;

}

void solve()

{

int i,j,k;

double u,v;

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

{

for(j=nt(i+1),k=nt(j+1);j!=i;j=nt(j+1))

{

u=area(i,j,k);

while(k!=i&&u<(v=area(i,j,nt(k+1))))

{

k=nt(k+1);

u=v;

}

mx=max(mx,u);

}

printf("%.2f\n",mx);

}

int main()

{

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

{

init();

solve();

}

return 0;

}

[POJ 2540]

发表回复

Hotter Colder

半平面交

题意：在大小为10*10的矩形内有一个“最热点”，矩形内离最热点越远越冷。初始位置（0，0），移动50次，每次给出移动的目标位置以及相对之前位置的温度变化情况。对于每次移动，需要计算可能存在最热点的区域面积。

分析：初始整个矩形都是可行的，每次移动结果若是“Hotter”或者“Colder”，相当于将之前的可行区域进行了切分；若是“Same”则可行区域变为线段，面积恒为0。每次切分可以用半平面来表示。求面积时，由于题目数据量很小，依然可以O(n^3)地处理。具体做法是，求出每两条直线间的交点（包括初始矩形对应的4条边线），然后用各半平面方程判可行，得到的可行点便是可行区域的边界点。接下来，取它们的中心，再按极坐标排序，依次求中心与每两相邻点围成三角形的面积，最后求和即可。干净利落的1A解决。

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

#define eps 1e-8

int el,pl,tag;
char s[100];

struct E
{
    double x1,y1,xd,yd;
    double a,b,c;
}e[50];

struct P
{
    double x,y,ang;
    bool operator < (const P& p) const
    {
        return ang<p.ang;
    }
}p[2000];

void init()
{
    e[el].x1=0; e[el].y1=0; e[el].xd=0; e[el].yd=10;
    e[el].a=1; e[el].b=0; e[el].c=0;
    el++;
    e[el].x1=0; e[el].y1=10; e[el].xd=10; e[el].yd=0;
    e[el].a=0; e[el].b=1; e[el].c=-10;
    el++;
    e[el].x1=10; e[el].y1=10; e[el].xd=0; e[el].yd=-10;
    e[el].a=1; e[el].b=0; e[el].c=-10;
    el++;
    e[el].x1=10; e[el].y1=0; e[el].xd=-10; e[el].yd=0;
    e[el].a=0; e[el].b=1; e[el].c=0;
    el++;
}

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

void adde(double x1,double y1,double x2,double y2)
{
    double x3=(x1+x2)/2,y3=(y1+y2)/2;
    double ang=atan2(x2-x1,y1-y2);
    double x4=x3+1.0*cos(ang),y4=y3+1.0*sin(ang);
    e[el].x1=x3; e[el].y1=y3;
    e[el].xd=x4-x3; e[el].yd=y4-y3;
    e[el].a=y3-y4; e[el].b=x4-x3;
    e[el].c=(y4-y3)*x3-(x4-x3)*y3;
    if(abs(e[el].a)<eps)
    {
        e[el].a=0;
        e[el].c/=e[el].b;
        e[el].b=1;
    }
    else
    {
        e[el].b/=e[el].a;
        e[el].c/=e[el].a;
        e[el].a=1;
    }
    el++;
}

double clcd()
{
    if(tag)
        return 0;
    pl=0;
    int i,j,k,l;
    double x,y,xm=0,ym=0,d=0;
    double a1,b1,c1,a2,b2,c2;
    for(i=0;i<el-1;i++)
    {
        a1=e[i].a; b1=e[i].b; c1=e[i].c;
        for(j=i+1;j<el;j++)
        {
            a2=e[j].a; b2=e[j].b; c2=e[j].c;
            if(abs(a1-a2)<eps&&abs(b1-b2)<eps)
                continue;
            if(abs(a1)<eps)
            {
                y=-c1/b1;
                x=(-c2-b2*y)/a2;
            }
            else
            {
                y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
                x=(-c1-b1*y)/a1;
            }
            p[pl].x=x;
            p[pl].y=y;
            pl++;
        }
    }
    for(i=j=0;i<pl;i++)
    {
        x=p[i].x;
        y=p[i].y;
        for(l=0;l<el;l++)
        {
            if(crs(x-e[l].x1,y-e[l].y1,e[l].xd,e[l].yd)<-eps)
                break;
        }
        if(l==el)
        {
            xm+=x;
            ym+=y;
            p[j++]=p[i];
        }
    }
    pl=j;
    xm/=pl;
    ym/=pl;
    for(i=0;i<pl;i++)
        p[i].ang=atan2(p[i].x-xm,p[i].y-ym);
    sort(p,p+pl);
    for(i=0;i<pl;i++)
    {
        j=(i+1)%pl;
        d+=abs(crs(xm-p[i].x,ym-p[i].y,xm-p[j].x,ym-p[j].y))*0.5;
    }
    return d;
}

void solve()
{
    int i,j,k,l;
    double x1=0,y1=0,x2,y2;
    while(~scanf("%lf%lf%s",&x2,&y2,s))
    {
        if(s[0]=='H')
            adde(x1,y1,x2,y2);
        else if(s[0]=='C')
            adde(x2,y2,x1,y1);
        else
            tag=1;
        x1=x2;
        y1=y2;
        printf("%.2f\n",clcd());
    }
}

int main()
{
    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

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

int el,pl,tag;

char s[100];

struct E

{

double x1,y1,xd,yd;

double a,b,c;

}e[50];

struct P

{

double x,y,ang;

bool operator < (const P& p) const

{

return ang<p.ang;

}

}p[2000];

void init()

{

e[el].x1=0; e[el].y1=0; e[el].xd=0; e[el].yd=10;

e[el].a=1; e[el].b=0; e[el].c=0;

el++;

e[el].x1=0; e[el].y1=10; e[el].xd=10; e[el].yd=0;

e[el].a=0; e[el].b=1; e[el].c=-10;

el++;

e[el].x1=10; e[el].y1=10; e[el].xd=0; e[el].yd=-10;

e[el].a=1; e[el].b=0; e[el].c=-10;

el++;

e[el].x1=10; e[el].y1=0; e[el].xd=-10; e[el].yd=0;

e[el].a=0; e[el].b=1; e[el].c=0;

el++;

}

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

{

return x1*y2-x2*y1;

}

void adde(double x1,double y1,double x2,double y2)

{

double x3=(x1+x2)/2,y3=(y1+y2)/2;

double ang=atan2(x2-x1,y1-y2);

double x4=x3+1.0*cos(ang),y4=y3+1.0*sin(ang);

e[el].x1=x3; e[el].y1=y3;

e[el].xd=x4-x3; e[el].yd=y4-y3;

e[el].a=y3-y4; e[el].b=x4-x3;

e[el].c=(y4-y3)*x3-(x4-x3)*y3;

if(abs(e[el].a)<eps)

{

e[el].a=0;

e[el].c/=e[el].b;

e[el].b=1;

}

else

{

e[el].b/=e[el].a;

e[el].c/=e[el].a;

e[el].a=1;

}

el++;

}

double clcd()

{

if(tag)

return 0;

pl=0;

int i,j,k,l;

double x,y,xm=0,ym=0,d=0;

double a1,b1,c1,a2,b2,c2;

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

{

a1=e[i].a; b1=e[i].b; c1=e[i].c;

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

{

a2=e[j].a; b2=e[j].b; c2=e[j].c;

if(abs(a1-a2)<eps&&abs(b1-b2)<eps)

continue;

if(abs(a1)<eps)

{

y=-c1/b1;

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

}

else

{

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

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

}

p[pl].x=x;

p[pl].y=y;

pl++;

}

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

{

x=p[i].x;

y=p[i].y;

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

{

if(crs(x-e[l].x1,y-e[l].y1,e[l].xd,e[l].yd)<-eps)

break;

}

if(l==el)

{

xm+=x;

ym+=y;

p[j++]=p[i];

}

pl=j;

xm/=pl;

ym/=pl;

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

p[i].ang=atan2(p[i].x-xm,p[i].y-ym);

sort(p,p+pl);

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

{

j=(i+1)%pl;

d+=abs(crs(xm-p[i].x,ym-p[i].y,xm-p[j].x,ym-p[j].y))*0.5;

}

return d;

}

void solve()

{

int i,j,k,l;

double x1=0,y1=0,x2,y2;

while(~scanf("%lf%lf%s",&x2,&y2,s))

{

if(s[0]=='H')

adde(x1,y1,x2,y2);

else if(s[0]=='C')

adde(x2,y2,x1,y1);

else

tag=1;

x1=x2;

y1=y2;

printf("%.2f\n",clcd());

}

int main()

{

init();

solve();

return 0;

}

[POJ 3384]

发表回复

Feng Shui

半平面交

题意：给出一个凸多边形描述，问如何在凸多边形内放两个半径都为r的圆，使两圆覆盖区域并集的面积最大。两圆可以重叠，但重叠部分面积不累加。圆不能超出凸多边形的边界。题目保证有解，若有多解，输出任意一组。

根据题意，目标要使两圆重叠区域最小。很容易推出可行的圆心区域是原凸多边形各边向内“塌缩”r后围成的新多边形。那么，在这个新多边形内，找出距离最远的两个端点即可。

实现起来也不太难，由于数据规模不大（n最多100），直接用了O(n^3)的方法。具体做法是，首先算出各边沿斜率直角方向向内平移r后的新方程，然后求各直线间的交点。由于塌缩后，某些直线会完全位于有效区域之外，因此，对于这O(n^2)个交点，需要再用n条新直线方程判是否有效。最后，在剩余的交点中找出距离最远的两个即可。

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

#define eps 1e-8

int n,mxi,mxj;
double r,x[10000],y[10000],mx;

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

void init()
{
    int i,j;
    double ang,x1,y1,x2,y2;
    mx=-1;
    for(i=0;i<n;i++)
        scanf("%lf%lf",x+i,y+i);
    for(i=0;i<n;i++)
    {
        j=(i+1)%n;
        x1=x[i]; y1=y[i]; x2=x[j]; y2=y[j];
        ang=atan2(x1-x2,y2-y1);
        x1+=r*cos(ang); y1+=r*sin(ang);
        x2+=r*cos(ang); y2+=r*sin(ang);
        e[i].x1=x1; e[i].y1=y1; e[i].x2=x2; e[i].y2=y2;
        e[i].a=y1-y2;
        e[i].b=x2-x1;
        e[i].c=(y2-y1)*x1-(x2-x1)*y1;
        if(abs(e[i].a)<eps)
        {
            e[i].a=0;
            e[i].c/=e[i].b;
            e[i].b=1;
        }
        else
        {
            e[i].b/=e[i].a;
            e[i].c/=e[i].a;
            e[i].a=1;
        }
    }
}

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

void solve()
{
    int i,j,k,l;
    double a1,b1,c1,a2,b2,c2,d;
    for(i=k=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            a1=e[i].a; b1=e[i].b; c1=e[i].c;
            a2=e[j].a; b2=e[j].b; c2=e[j].c;
            if(abs(a1-a2)<eps&&abs(b1-b2)<eps)
                continue;
            if(abs(a1)<eps)
            {
                y[k]=-c1/b1;
                x[k]=(-c2-b2*y[k])/a2;
            }
            else
            {
                y[k]=(a2*c1-a1*c2)/(a1*b2-a2*b1);
                x[k]=(-c1-b1*y[k])/a1;
            }
            k++;
        }
    }
    for(i=l=0;i<k;i++)
    {
        for(j=0;j<n;j++)
        {
            if(crs(e[j].x1,e[j].y1,x[i],y[i],e[j].x2,e[j].y2)<-eps)
                break;
        }
        if(j==n)
        {
            x[l]=x[i];
            y[l]=y[i];
            l++;
        }
    }
    for(i=0;i<l-1;i++)
    {
        for(j=i+1;j<l;j++)
        {
            d=pow(x[i]-x[j],2)+pow(y[i]-y[j],2);
            if(d>mx)
            {
                mx=d;
                mxi=i;
                mxj=j;
            }
        }
    }
    printf("%.4f %.4f %.4f %.4f\n",x[mxi],y[mxi],x[mxj],y[mxj]);
}

int main()
{
    while(~scanf("%d%lf",&n,&r))
    {
        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

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

int n,mxi,mxj;

double r,x[10000],y[10000],mx;

struct E

{

double x1,y1,x2,y2;

double a,b,c;

}e[100];

void init()

{

int i,j;

double ang,x1,y1,x2,y2;

mx=-1;

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

scanf("%lf%lf",x+i,y+i);

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

{

j=(i+1)%n;

x1=x[i]; y1=y[i]; x2=x[j]; y2=y[j];

ang=atan2(x1-x2,y2-y1);

x1+=r*cos(ang); y1+=r*sin(ang);

x2+=r*cos(ang); y2+=r*sin(ang);

e[i].x1=x1; e[i].y1=y1; e[i].x2=x2; e[i].y2=y2;

e[i].a=y1-y2;

e[i].b=x2-x1;

e[i].c=(y2-y1)*x1-(x2-x1)*y1;

if(abs(e[i].a)<eps)

{

e[i].a=0;

e[i].c/=e[i].b;

e[i].b=1;

}

else

{

e[i].b/=e[i].a;

e[i].c/=e[i].a;

e[i].a=1;

}

double crs(double x0,double y0,double x1,double y1,

double x2,double y2)

{

x1-=x0; y1-=y0; x2-=x0; y2-=y0;

return x1*y2-x2*y1;

}

void solve()

{

int i,j,k,l;

double a1,b1,c1,a2,b2,c2,d;

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

{

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

{

a1=e[i].a; b1=e[i].b; c1=e[i].c;

a2=e[j].a; b2=e[j].b; c2=e[j].c;

if(abs(a1-a2)<eps&&abs(b1-b2)<eps)

continue;

if(abs(a1)<eps)

{

y[k]=-c1/b1;

x[k]=(-c2-b2*y[k])/a2;

}

else

{

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

x[k]=(-c1-b1*y[k])/a1;

}

k++;

}

for(i=l=0;i<k;i++)

{

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

{

if(crs(e[j].x1,e[j].y1,x[i],y[i],e[j].x2,e[j].y2)<-eps)

break;

}

if(j==n)

{

x[l]=x[i];

y[l]=y[i];

l++;

}

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

{

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

{

d=pow(x[i]-x[j],2)+pow(y[i]-y[j],2);

if(d>mx)

{

mx=d;

mxi=i;

mxj=j;

}

printf("%.4f %.4f %.4f %.4f\n",x[mxi],y[mxi],x[mxj],y[mxj]);

}

int main()

{

while(~scanf("%d%lf",&n,&r))

{

init();

solve();

}

return 0;

}