[POJ 3130] | Eurce's Blog

How I Mathematician Wonder What You Are!

判断多边形内核。

题意为N个顶点逆时针顺序描述的一个多边形，要求判断该多边形是否有“内核”。所谓“内核”，就是在该多边形内的一块区域，站在这块区域内任意一点观察多边形的内部，都可以无死角地看遍整个多边形。

解这题涉及到半平面的概念。其实就是每条线段都会将平面区域划分成两部分，一部分包含多边形内部，一部分不包含。那么，将所有线段对应的包含多边形内部那一半的平面区域求交集，就得到了多边形的内核（如果存在）或者空集（不存在内核）。

进一步考虑实现问题的话，可以将每条直线描述为ax+by+c=0，那么半平面方程即为ax+by+c>=0，其中a、b、c三个系数，根据直线的朝向以及题目给定的逆时针顺序，a是取-1或1的，进而可以确定b和c。多边形的内核区域，可以抽象为某些点，进一步分析可以发现，若存在内核，则其角一定是某两条边所在直线的交点。由于最多只有50条边，那么可以枚举n(n-1)/2个交点，依次代入n个半平面方程，看是否存在点满足对所有半平面方程都大于0即可。

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

#define eps 1e-8

int n,el,ll,hd;
double x[50],y[50];

struct L
{
    double a,b,c;
}l[50];

struct E
{
    double x,y;
    E(double a,double b): x(a),y(b) {};
};

list<E>L;

inline double abs(double a)
{
    return a>0?a:-a;
}

inline void addl(double x1,double y1,double x2,double y2)
{
    double xd,yd,a,b,c;
    if(abs(xd=x2-x1)<eps)
    {
        if(y2<y1)
        {
            a=1;
            c=-x1;
        }
        else
        {
            a=-1;
            c=x1;
        }
        b=0;
    }
    else if(abs(yd=y2-y1)<eps)
    {
        a=0;
        if(x2>x1)
        {
            b=1;
            c=-y1;
        }
        else
        {
            b=-1;
            c=y1;
        }
    }
    else
    {
        a=1;
        b=(x2-x1)/(y1-y2);
        c=-x1-b*y1;
        if(yd>0)
        {
            a=-a; b=-b; c=-c;
        }
    }
    l[ll].a=a; l[ll].b=b; l[ll].c=c; ll++;
}

inline void adde(int i,int j)
{
    double a1=l[i].a,b1=l[i].b,c1=l[i].c;
    double a2=l[j].a,b2=l[j].b,c2=l[j].c;
    if(abs(a1)<eps&&abs(a2)<eps||abs(b1)<eps&&abs(b2)<eps)
        return;
    if(abs(a1/b1-a2/b2)<eps)
        return;
    double x,y;
    if(abs(a1)<eps)
    {
        y=-c1/b1;
        x=-(b2*y+c2)/a2;
    }
    else if(abs(b1)<eps)
    {
        x=-c1/a1;
        y=-(c2+a2*x)/b2;
    }
    else
    {
        y=(a2/a1*c1-c2)/(b2-a2/a1*b1);
        x=-(b1*y+c1)/a1;
    }
    L.push_back(E(x,y));
}

void init()
{
    int i,j,k;
    L.clear();
    hd=-1;
    el=ll=0;
    for(i=0;i<n;i++)
        scanf("%lf%lf",&x[i],&y[i]);
    for(i=0;i<n-1;i++)
        addl(x[i],y[i],x[i+1],y[i+1]);
    addl(x[n-1],y[n-1],x[0],y[0]);
    for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
            adde(i,j);
}

void solve()
{
    int i,j,k;
    double a,b,c,x,y;
    list<E>::iterator lit;
    for(i=0;i<ll;i++)
    {
        a=l[i].a; b=l[i].b; c=l[i].c;
        for(lit=L.begin();lit!=L.end();)
        {
            x=lit->x; y=lit->y;
            if(a*x+b*y+c<-eps)
                L.erase(lit++);
            else
                lit++;
        }
    }
    if(L.size())
        puts("1");
    else
        puts("0");
}

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

#include<cstdio>

#include<cstring>

#include<list>

using namespace std;

#define eps 1e-8

int n,el,ll,hd;

double x[50],y[50];

struct L

{

double a,b,c;

}l[50];

struct E

{

double x,y;

E(double a,double b): x(a),y(b) {};

};

list<E>L;

inline double abs(double a)

{

return a>0?a:-a;

}

inline void addl(double x1,double y1,double x2,double y2)

{

double xd,yd,a,b,c;

if(abs(xd=x2-x1)<eps)

{

if(y2<y1)

{

a=1;

c=-x1;

}

else

{

a=-1;

c=x1;

}

b=0;

}

else if(abs(yd=y2-y1)<eps)

{

a=0;

if(x2>x1)

{

b=1;

c=-y1;

}

else

{

b=-1;

c=y1;

}

else

{

a=1;

b=(x2-x1)/(y1-y2);

c=-x1-b*y1;

if(yd>0)

{

a=-a; b=-b; c=-c;

}

l[ll].a=a; l[ll].b=b; l[ll].c=c; ll++;

}

inline void adde(int i,int j)

{

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

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

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

return;

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

return;

double x,y;

if(abs(a1)<eps)

{

y=-c1/b1;

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

}

else if(abs(b1)<eps)

{

x=-c1/a1;

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

}

else

{

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

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

}

L.push_back(E(x,y));

}

void init()

{

int i,j,k;

L.clear();

hd=-1;

el=ll=0;

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

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

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

addl(x[i],y[i],x[i+1],y[i+1]);

addl(x[n-1],y[n-1],x[0],y[0]);

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

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

adde(i,j);

}

void solve()

{

int i,j,k;

double a,b,c,x,y;

list<E>::iterator lit;

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

{

a=l[i].a; b=l[i].b; c=l[i].c;

for(lit=L.begin();lit!=L.end();)

{

x=lit->x; y=lit->y;

if(a*x+b*y+c<-eps)

L.erase(lit++);

else

lit++;

}

if(L.size())

puts("1");

else

puts("0");

}

int main()

{

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

{

init();

solve();

}

return 0;

}

最近都在练习计算几何的题目。感觉这类题有个特点是比较偏数学公式的推导，对复杂度的要求不会太高。

借这个机会好好复习下各种几何工具吧。