【kuangbin专题】计算几何_半平面交

1.poj3335 Rotating Scoreboard

传送：http://poj.org/problem?id=3335

题意：就是有个球场，球场的形状是个凸多边形，然后观众是坐在多边形的边上的，问你是否在球场上有个地方可以放一个记分牌，然后所有的观众都可以看得到的。

分析：多边形是否存在内核。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=110;
const double eps=1e-8;
int sgn(double x){
    if (fabs(x)<eps) return 0;
    if (x<0) return -1;
    return 1;
}
struct point{
    double x,y;
    point(){}
    point(double _x,double _y):x(_x),y(_y){}
    point operator -(const point &b)const{
        return point(x-b.x,y-b.y);
    }
    double operator ^(const point &b)const{
        return x*b.y-y*b.x;
    }
}p[maxn];
struct line{
    point s,e;
    line(){}
    line(point _s,point _e):s(_s),e(_e){}
    point crosspoint(line v){
        int a1=(v.e-v.s)^(s-v.s),a2=(v.e-v.s)^(e-v.s);
        return point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
    }
    //两向量平行（对应直线平行或重合）
    bool parallel(line v){
        return sgn((e-s)^(v.e-v.s))==0;
    } 
};
struct halfplane:public line{
    double angle;
    halfplane(){}
    halfplane(line v){s=v.s;e=v.e;}
    void calcangle(){
        angle=atan2(e.y-s.y,e.x-s.x);
    }
    bool operator <(const halfplane &b)const{
        return angle<b.angle;
    }
};
struct halfplanes{
    int n;
    halfplane hp[maxn];
    point p[maxn];
    int que[maxn]; int st,ed;  //双端队列
    void push(halfplane tmp){hp[n++]=tmp;}
    //去重
    void unique(){
        int m=1;
        for (int i=1;i<n;i++){
            if (sgn(hp[i].angle-hp[i-1].angle)!=0) hp[m++]=hp[i];
            else if (sgn((hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s))>0) hp[m-1]=hp[i];
        }
        n=m;
    } 
    bool halfplaneinsert(){
        for (int i=0;i<n;i++) hp[i].calcangle();
        sort(hp,hp+n);
        unique();
        que[st=0]=0; que[ed=1]=1;
        p[1]=hp[0].crosspoint(hp[1]);
        for (int i=2;i<n;i++){
            while (st<ed && sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0) ed--;
            while (st<ed && sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0) st++;
            que[++ed]=i;
            if (hp[i].parallel(hp[que[ed-1]])) return false;
            p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
        }
        while (st<ed && sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0) ed--;
        while (st<ed && sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0) st++;
        if (st+1>=ed) return false; else return true;
    }
};
halfplanes ha;
int main(){
    int t,n; cin >>t;
    while (t--){
        cin >> n;
        ha.n=0;
        for (int i=0;i<n;i++) cin >> p[i].x >> p[i].y;
        for (int i=0;i<n;i++){
            ha.push(halfplane(line(p[i],p[(i-1+n)%n])));
        }
        if (ha.halfplaneinsert()) cout << "YES\n"; else cout << "NO\n";
    }
    return 0;
}

2.poj1279 Art Gallery

传送：http://poj.org/problem?id=1279

题意：给一个多边形（顺时针给出点），求内核面积。

分析：rt。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1505;
const double eps=1e-8;
int sgn(double x){
    if (fabs(x)<eps) return 0;
    if (x<0) return -1;
    return 1;
}
struct point{
    double x,y;
    point(){}
    point(double _x,double _y):x(_x),y(_y){}
    point operator -(const point &b)const{
        return point(x-b.x,y-b.y);
    }
    double operator ^(const point &b)const{
        return x*b.y-y*b.x;
    }
}p[maxn];
struct line{
    point s,e;
    line(){}
    line(point _s,point _e):s(_s),e(_e){}
    point crosspoint(line v){
        int a1=(v.e-v.s)^(s-v.s),a2=(v.e-v.s)^(e-v.s);
        return point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
    }
    //两向量平行（对应直线平行或重合）
    bool parallel(line v){
        return sgn((e-s)^(v.e-v.s))==0;
    } 
};
struct polygon{
    int n;
    point p[maxn];
    double getarea(){
        double sum=0;
        for (int i=0;i<n;i++) sum+=(p[i]^(p[(i+1)%n]));
        return fabs(sum)/2; 
    }
};
struct halfplane:public line{
    double angle;
    halfplane(){}
    halfplane(line v){s=v.s;e=v.e;}
    void calcangle(){
        angle=atan2(e.y-s.y,e.x-s.x);
    }
    bool operator <(const halfplane &b)const{
        return angle<b.angle;
    }
};
polygon C;
struct halfplanes{
    int n;
    halfplane hp[maxn];
    point p[maxn];
    int que[maxn]; int st,ed;  //双端队列
    void push(halfplane tmp){hp[n++]=tmp;}
    //去重
    void unique(){
        int m=1;
        for (int i=1;i<n;i++){
            if (sgn(hp[i].angle-hp[i-1].angle)!=0) hp[m++]=hp[i];
            else if (sgn((hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s))>0) hp[m-1]=hp[i];
        }
        n=m;
    } 
    bool halfplaneinsert(){
        for (int i=0;i<n;i++) hp[i].calcangle();
        sort(hp,hp+n);
        unique();
        que[st=0]=0; que[ed=1]=1;
        p[1]=hp[0].crosspoint(hp[1]);
        for (int i=2;i<n;i++){
            while (st<ed && sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0) ed--;
            while (st<ed && sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0) st++;
            que[++ed]=i;
            if (hp[i].parallel(hp[que[ed-1]])) return false;
            p[ed]=hp[i].crosspoint(hp[que[ed-1]]);
        }
        while (st<ed && sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0) ed--;
        while (st<ed && sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0) st++;
        if (st+1>=ed) return false; else return true;
    }
    //得到最后半平面交的凸多边形
    //得到先调用halfplaneinsert()，且返回true
    void getconvex(polygon &con){
        p[st]=hp[que[st]].crosspoint(hp[que[ed]]);
        con.n=ed-st+1;
        for (int j=st,i=0;j<=ed;j++,i++) con.p[i]=p[j];
    } 
};
halfplanes ha;
int main(){
    int t,n; cin >> t;
    while (t--){
        cin >> n;
        for (int i=0;i<n;i++) cin >> p[i].x >> p[i].y;
        ha.n=0;
        for (int i=0;i<n;i++) ha.push(line(p[i],p[(i-1+n)%n]));
        ha.halfplaneinsert();
        C.n=0;
        ha.getconvex(C);
        printf("%.2f\n",C.getarea());
    }
    return 0;
} 

3.poj3525 Most Distant Point from the Sea

传送：http://poj.org/problem?id=3525

题意：给出一个海岛，求出岛上离海最远的点。输出距离。

分析：半平面交+二分。就是求多边形的最大半径圆   //板子

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-8;
const int maxn=110;
inline double sqr(double x){return x*x;}
int N;
int sgn(double x){
    if (fabs(x)<eps) return 0;
    if (x<0) return -1;
    return 1;
}
struct point{
    double x,y;
    point(){}
    point(double _x,double _y):x(_x),y(_y){}
    point operator -(const point &b)const{
        return point(x-b.x,y-b.y);
    }
    double operator ^(const point &b)const{
        return x*b.y-y*b.x;
    }
};
struct line{
    point s,e;
    double k; //斜率 
    line(){}
    line(point _s,point _e):s(_s),e(_e){k=atan2(e.y-s.y,e.x-s.x);}
    point operator &(const line &b)const{ //求两直线交点
        point res=s;
        double t=((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
        res.x+=(e.x-s.x)*t; res.y+=(e.y-s.y)*t;
        return res;
    }
};
point p[maxn]; //记录最初给的点集
line L[maxn]; //由最初的点集生成直线的集合
point pp[maxn]; //记录半平面交的结果的点集
//半平面交，直线的左边代表有效区域
bool HPIcmp(line a,line b){  //直线排序函数
    if(sgn(a.k-b.k)!=0) return a.k<b.k; //斜率排序
    //斜率相同我也不知道怎么办
    return ((a.s-b.s)^(b.e-b.s))<0;
}
void HPI(line L[],int n,point res[],int &resn){ 
//line是半平面交的直线的集合 n是直线的条数 res是结果
//的点集 resn是点集里面点的个数
    int tot=n;
    sort(L,L+n,HPIcmp);
    tot=1;
    //去掉斜率重复的
    for(int i=1;i<n;i++) if(sgn(L[i].k-L[i-1].k)!=0) L[tot++]=L[i];
    int head,tail; line Q[maxn];  //双端队列 
    Q[head=0]=L[0]; Q[tail=1]=L[1];
    resn=0;
    for(int i=2;i<tot;i++){
        if(sgn((Q[tail].e-Q[tail].s)^(Q[tail-1].e-Q[tail-1].s))==0||
        sgn((Q[head].e-Q[head].s)^(Q[head+1].e-Q[head+1].s))==0) return;
        while(head<tail && (((Q[tail]&Q[tail-1])-L[i].s)^(L[i].e-L[i].s))>eps) tail--;
        while(head<tail && (((Q[head]&Q[head+1])-L[i].s)^(L[i].e-L[i].s))>eps) head++;
        Q[++tail]=L[i];
    }
    while(head<tail && (((Q[tail]&Q[tail-1])-Q[head].s)^(Q[head].e-Q[head].s))>eps) tail--;
    while(head<tail && (((Q[head]&Q[head-1])-Q[tail].s)^(Q[tail].e-Q[tail].e))>eps) head++;
    if(tail<=head+1) return;
    for(int i=head;i<tail; i++) res[resn++]=Q[i]&Q[i+1];
    if(head<tail-1) res[resn++]=Q[head]&Q[tail];
}
double dist(point a,point b){
    return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
void change(point p1,point p2,point &a,point &b,double p){
    double len=dist(p1,p2);
    double dx=(p1.y-p2.y)*p/len,dy=(p2.x-p1.x)*p/len;
    a.x=p1.x+dx;a.y=p1.y+dy;
    b.x=p2.x+dx;b.y=p2.y+dy;
}
bool check(double mid){
    for (int i=0;i<N;i++){
        point a,b;
        change(p[i],p[(i+1)%N],a,b,mid);
        L[i]=line(a,b);
    }
    int resn;
    HPI(L,N,pp,resn); //resn等于0说明移多了
    if (resn==0) return false; else return true;    
}
int main(){
    while (cin >> N && N){
        for (int i=0;i<N;i++)
            cin >> p[i].x >> p[i].y;
        double l=0,r=100000,mid;
        double ans;
        while (r-l>=eps){
            mid=(l+r)/2;
            if (check(mid)){
                ans=mid;
                l=mid+eps;
            }
            else r=mid-eps;
        }
        printf("%.6f\n",ans);
    }
    return 0;
}

4.poj3384 Feng Shui

传送：http://poj.org/problem?id=3384

题意：给定两个同样大小的圆放置在多边形内（可以与多边形相切，两圆可以重叠），尽可能大的覆盖多边形面积，问两圆圆心。

分析：用半平面交将多边形的每条边一起向“内”推进R，得到新的多边形，然后求多边形的最远两点。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-8;
const int maxn=110;
inline double sqr(double x){return x*x;}
int n; double r;
int sgn(double x){
    if (fabs(x)<eps) return 0;
    if (x<0) return -1;
    return 1;
}
struct point{
    double x,y;
    point(){}
    point(double _x,double _y):x(_x),y(_y){}
    point operator -(const point &b)const{
        return point(x-b.x,y-b.y);
    }
    double operator ^(const point &b)const{
        return x*b.y-y*b.x;
    }
};
struct line{
    point s,e;
    double k; //斜率 
    line(){}
    line(point _s,point _e):s(_s),e(_e){k=atan2(e.y-s.y,e.x-s.x);}
    point operator &(const line &b)const{ //求两直线交点
        point res=s;
        double t=((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
        res.x+=(e.x-s.x)*t; res.y+=(e.y-s.y)*t;
        return res;
    }
};
point p[maxn]; //记录最初给的点集
line L[maxn]; //由最初的点集生成直线的集合
point pp[maxn]; //记录半平面交的结果的点集
//半平面交，直线的左边代表有效区域
bool HPIcmp(line a,line b){  //直线排序函数
    if(sgn(a.k-b.k)!=0) return a.k<b.k; //斜率排序
    //斜率相同我也不知道怎么办
    return ((a.s-b.s)^(b.e-b.s))<0;
}
void HPI(line L[],int n,point res[],int &resn){ 
//line是半平面交的直线的集合 n是直线的条数 res是结果
//的点集 resn是点集里面点的个数
    int tot=n;
    sort(L,L+n,HPIcmp);
    tot=1;
    //去掉斜率重复的
    for(int i=1;i<n;i++) if(sgn(L[i].k-L[i-1].k)!=0) L[tot++]=L[i];
    int head,tail; line Q[maxn];  //双端队列 
    Q[head=0]=L[0]; Q[tail=1]=L[1];
    resn=0;
    for(int i=2;i<tot;i++){
        if(sgn((Q[tail].e-Q[tail].s)^(Q[tail-1].e-Q[tail-1].s))==0||
        sgn((Q[head].e-Q[head].s)^(Q[head+1].e-Q[head+1].s))==0) return;
        while(head<tail && (((Q[tail]&Q[tail-1])-L[i].s)^(L[i].e-L[i].s))>eps) tail--;
        while(head<tail && (((Q[head]&Q[head+1])-L[i].s)^(L[i].e-L[i].s))>eps) head++;
        Q[++tail]=L[i];
    }
    while(head<tail && (((Q[tail]&Q[tail-1])-Q[head].s)^(Q[head].e-Q[head].s))>eps) tail--;
    while(head<tail && (((Q[head]&Q[head-1])-Q[tail].s)^(Q[tail].e-Q[tail].e))>eps) head++;
    if(tail<=head+1) return;
    for(int i=head;i<tail; i++) res[resn++]=Q[i]&Q[i+1];
    if(head<tail-1) res[resn++]=Q[head]&Q[tail];
}
double dist(point a,point b){
    return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
void change(point p1,point p2,point &a,point &b,double p){
    double len=dist(p1,p2);
    double dx=(p1.y-p2.y)*p/len,dy=(p2.x-p1.x)*p/len;
    a.x=p1.x+dx;a.y=p1.y+dy;
    b.x=p2.x+dx;b.y=p2.y+dy;
}
int main(){
    while (cin >> n >> r){
        for (int i=0;i<n;i++) cin >> p[i].x >> p[i].y;
        reverse(p,p+n);
        for (int i=0;i<n;i++){
            point a,b;
            change(p[i],p[(i+1)%n],a,b,r);
            L[i]=line(a,b);
        }
        int resn;
        HPI(L,n,pp,resn); //resn等于0说明移多了
        int res1=0,res2=0;
        for (int i=0;i<resn;i++)
            for (int j=i+1;j<resn;j++){
                if (dist(pp[i],pp[j])>dist(pp[res1],pp[res2])) res1=i,res2=j;
            }
        printf("%.5f %.5f %.5f %.5f\n",pp[res1].x,pp[res1].y,pp[res2].x,pp[res2].y);
    }
    return 0;
}

5.poj2540 Hotter Colder

传送：http://poj.org/problem?id=2540

题意：在10×10的房间里，有一个点放有宝藏。从（0,0）开始，每次走一个点，告诉你距离宝藏更近or更远，每次输出宝藏可能所在区域的面积。

分析：半平面交解线性规划问题。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
const double eps=1e-8;
const int maxn=110;
int sgn(double x){
    if (fabs(x)<eps) return 0;
    if (x<0) return -1;
    return 1;
}
struct point{
    double x,y;
    point(){}
    point(double _x,double _y):x(_x),y(_y){}
    point operator +(const point &b)const{
        return point(x+b.x,y+b.y);
    }
    point operator -(const point &b)const{
        return point(x-b.x,y-b.y);
    }
    double operator ^(const point &b)const{
        return x*b.y-y*b.x;
    }
    point operator *(double k)const{
        return point(x*k,y*k);
    }
};
point pp[maxn];
struct line{
    point p,v;
    double k;
    line(){}
    line(point a,point b):p(a),v(b){k=atan2(v.y,v.x);}
    bool operator <(const line &b)const{
        return k<b.k;
    }
};
line L[maxn],q[maxn];
bool left(const line &l,const point &p){
    return (l.v^(p-l.p))>0;   //点在线的上方 
}
point pos(const line &a,const line &b){
    point x=a.p-b.p;
    double t=(b.v^x)/(a.v^b.v);
    return a.p+a.v*t;
}
int HalfplaneIntersection(line L[],int n,point poly[]){
    sort(L,L+n);
    int first,last;
    point *p=new point[n];
    line *q=new line[n];
    q[first=last=0] = L[0];
    for(int i=1;i<n;i++){
        while(first < last && !left(L[i],p[last-1])) last--;
        while(first < last && !left(L[i],p[first])) first++;
        q[++last] = L[i];
        if(fabs((q[last].v^q[last-1].v))<eps) {
            last--;
            if(left(q[last],L[i].p)) q[last] = L[i];
        }
        if(first<last) p[last-1]=pos(q[last-1],q[last]);
    }
    while(first<last && !left(q[first],p[last-1])) last--;
    if(last-first <=1) return 0;
    p[last]=pos(q[last],q[first]);
    int m=0;
    for(int i=first;i<=last;i++) poly[m++]=p[i];
    return m;
}
double dist(point a){
    return sqrt(a.x*a.x+a.y*a.y);
}
point normal(point b) {
    double len=dist(b);
    return point(-b.y/len,b.x/len);
}
double getarea(point p[],int n){
    double sum=0;
    for (int i=0;i<n;i++) sum+=(p[i]^(p[(i+1)%n]));
    return fabs(sum)/2;
}
int main(){
    L[0]=line(point(0,0),point(10,0)-point(0,0));
    L[1]=line(point(10,0),point(10,10)-point(10,0));
    L[2]=line(point(10,10),point(0,10)-point(10,10));
    L[3]=line(point(0,10),point(0,0)-point(0,10));
    int cnt=4;
    double x1=0,y1=0,x2,y2; string ch;
    int f=1;
    while (cin >> x2 >> y2 >> ch){
        point a=point((x1+x2)/2,(y1+y2)/2),b;
        if (!f){cout << "0.00\n";continue;}
        if (ch[0]=='H') b=normal(point(x1,y1)-point(x2,y2));  
        else if (ch[0]=='C') b=normal(point(x2,y2)-point(x1,y1));  
        else{cout << "0.00\n";f=0;continue;}
        L[cnt++]=line(a,b);
        int xx=HalfplaneIntersection(L,cnt,pp);
        if (xx==0){cout << "0.00\n";f=0;continue;}
        else{
            double ans=getarea(pp,xx);
            printf("%.2f\n",ans);
            if (sgn(ans)==0) f=0; 
        }
        x1=x2;y1=y2;
    } 
    return 0;
} 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
const double eps=1e-8;
const int maxn=110;
inline double sqr(double x){return x*x;}
int n; double r;
int sgn(double x){
    if (fabs(x)<eps) return 0;
    if (x<0) return -1;
    return 1;
}
struct point{
    double x,y;
    point(){}
    point(double _x,double _y):x(_x),y(_y){}
    point operator -(const point &b)const{
        return point(x-b.x,y-b.y);
    }
    double operator ^(const point &b)const{
        return x*b.y-y*b.x;
    }
};
struct line{
    point s,e;
    double k; //斜率 
    line(){}
    line(point _s,point _e):s(_s),e(_e){k=atan2(e.y-s.y,e.x-s.x);}
    point operator &(const line &b)const{ //求两直线交点
        point res=s;
        double t=((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
        res.x+=(e.x-s.x)*t; res.y+=(e.y-s.y)*t;
        return res;
    }
};
line L[maxn]; //由最初的点集生成直线的集合
point pp[maxn]; //记录半平面交的结果的点集
//半平面交，直线的左边代表有效区域
bool HPIcmp(line a,line b){  //直线排序函数
    if(sgn(a.k-b.k)!=0) return a.k<b.k; //斜率排序
    return ((a.s-b.s)^(b.e-b.s))<0;
}
void HPI(line L[],int n,point res[],int &resn){ 
    int tot=n;
    sort(L,L+n,HPIcmp);
    tot=1;
    //去掉斜率重复的
    for(int i=1;i<n;i++) if(sgn(L[i].k-L[i-1].k)!=0) L[tot++]=L[i];
    int head,tail; line Q[maxn];  //双端队列 
    Q[head=0]=L[0]; Q[tail=1]=L[1];
    resn=0;
    for(int i=2;i<tot;i++){
        if(sgn((Q[tail].e-Q[tail].s)^(Q[tail-1].e-Q[tail-1].s))==0||
        sgn((Q[head].e-Q[head].s)^(Q[head+1].e-Q[head+1].s))==0) return;
        while(head<tail && (((Q[tail]&Q[tail-1])-L[i].s)^(L[i].e-L[i].s))>eps) tail--;
        while(head<tail && (((Q[head]&Q[head+1])-L[i].s)^(L[i].e-L[i].s))>eps) head++;
        Q[++tail]=L[i];
    }
    while(head<tail && (((Q[tail]&Q[tail-1])-Q[head].s)^(Q[head].e-Q[head].s))>eps) tail--;
    while(head<tail && (((Q[head]&Q[head-1])-Q[tail].s)^(Q[tail].e-Q[tail].e))>eps) head++;
    if(tail<=head+1) return;
    for(int i=head;i<tail; i++) res[resn++]=Q[i]&Q[i+1];
    if(head<tail-1) res[resn++]=Q[head]&Q[tail];
}
double getarea(point p[],int n){
    double sum=0;
    for (int i=0;i<n;i++) sum+=(p[i]^p[(i+1)%n]);
    return fabs(sum)/2;
}
// 将向量 AB 逆时针旋转角度A
inline point Revolve(double cosA, double sinA, point A, point B){ 
    point B_;
    B_.x = (B.x - A.x) * cosA - (B.y - A.y) * sinA + A.x;
    B_.y = (B.x - A.x) * sinA + (B.y - A.y) * cosA + A.y;
    return B_;
}
int main(){
    L[0]=line(point(0,0),point(10,0));
    L[1]=line(point(10,0),point(10,10));
    L[2]=line(point(10,10),point(0,10));
    L[3]=line(point(0,10),point(0,0));
    int cnt=4;
    double x1=0,y1=0,x2,y2; string ch;
    int f=1;
    while (cin >> x2 >> y2 >> ch){
        point a=point((x1+x2)/2,(y1+y2)/2),b;
        int resn;
        if (!f){cout << "0.00\n";continue;}
        if (ch[0]=='C'){
            b=Revolve(0,1,a,point(x2,y2));
        }
        else if (ch[0]=='H'){
            b=Revolve(0,-1,a,point(x2,y2));
        }
        else{cout << "0.00\n";f=0;continue;}
        L[cnt++]=line(a,b);
        HPI(L,cnt,pp,resn);
        if (resn==0){cout << "0.00\n";f=0;continue;} 
        else{
            double area=getarea(pp,resn);
            printf("%.2f\n",area);
        }
        x1=x2;y1=y2;
    } 
    return 0;
}