[POJ 2540] | Eurce's Blog

半平面交

题意：在大小为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;

}