凸包( 一 )

A - Wall

题意：
建立围墙将城堡围起来，要求围墙至少距离城堡L，拐角处用圆弧取代，求围墙的长度。
题解：
答案是凸包周长加上一个圆周长。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=1010;
const double PI=acos(-1.0);
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
Point in[MAXN],out[MAXN];
Vector operator +(Vector A,Vector B)
{
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
bool operator <(const Point& a,const Point &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
int convexHull(Point *p,int n,Point *ch)
{
    sort(p,p+n);
    int m=0;
    for(int i=0;i<n;i++)
    {
        while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--)
    {
        while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    if(n>1) m--;
    return m;
}
double length(Vector A)
{
    return sqrt(A.x*A.x+A.y*A.y);
}
double  perimeter(Point *p,int n)
{
    double len=0;
    for(int i=0;i<n-1;i++)
    {
        len+=length(p[i+1]-p[i]);
    }
    len+=length(p[0]-p[n-1]);
    return len;
}
int main()
{
    int n,cnt;
    double l,ans;
    while(scanf("%d%lf",&n,&l)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&in[i].x,&in[i].y);
        }
        cnt=convexHull(in,n,out);
        ans=perimeter(out,cnt);
        printf("%.f\n",ans+2*PI*l);
    }
}

B - Scrambled Polygon
题意：
给出一个多边形的起点和n-1个乱序的坐标点，要求从起点逆序输出左边点
题解：
用叉积进行排序

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=500000;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
};
Point s(0.0,0.0);
Point point[MAXN];
typedef Point Vector;
Vector operator -(Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
int cmp(Point a,Point b)
{
    return cross(a-s,b-s)>0;
}
int main()
{
    double x,y;
    int cnt=0;
    scanf("%lf%lf",&s.x,&s.y);
    while(scanf("%lf%lf",&x,&y)!=EOF)
    {
        point[++cnt]=Point(x,y);
    }
    sort(point+1,point+1+cnt,cmp);
    printf("(%.f,%.f)\n",s.x,s.y);
    for(int i=1;i<=cnt;i++)
    {
        printf("(%.f,%.f)\n",point[i].x,point[i].y);
    }
}

C - The Fortified Forest
待填坑！！！
待填坑！！！
待填坑！！！
E - Cows
题解：
求凸包面积再除以５０

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=10010;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
Point in[MAXN],out[MAXN];
bool operator <(const Point &a,const Point &b )
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
Vector operator -(Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
int convexHull(Point *p,int n,Point *ch)
{
    sort(p,p+n);
    int m=0;
    for(int i=0;i<n;i++)
    {
        while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--)
    {
        while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    if(n>1) m--;
    return m;
}
double polyArea(Point *p,int n)
{
    double area=0.0;
    for(int i=1;i<n-1;i++)
    {
        area+=cross(p[i]-p[0],p[i+1]-p[0]);
    }
    return area/2;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&in[i].x,&in[i].y);
        }
        int ans=convexHull(in,n,out);
        double area=polyArea(out,ans);
        int res=(int)(area/50);
        printf("%d\n",res);
    }
}

Separate Points
题意：

有黑白两种颜色的点，判断是否可以用一条直线划分成颜色一致的两部分(输入点无坐标相同的点,直线上不能有输入点)


题解：
分别求出黑点的凸包，再求出白点的凸包，如果两个凸包可以分离,那么可以用直线划分；
可以分离的充要条件是两个凸包的边界和内部没有公共部分（哪怕一个点也不行）
（一）任取一个黑点，判断是否在白凸包内部；如果是，则无解；否则，再取白点，判断是否在凸包的内部，如果是，则无解
（二）任取黑凸包的线段判断是否和白凸包的线段是否规范相交，如果是，则无解
以上两个条件都满足才可以划分点集

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=110;
const int INF=0x7fffffff;
const double EPS=1e-10;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
};
Point white[MAXN],black[MAXN],wout[MAXN],bout[MAXN];
typedef Point Vector;
Vector operator -(Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
bool operator <(const Point &a,const Point &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
double dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
int convexHull(Point *p,int n,Point *ch)
{
    sort(p,p+n);
    int m=0;
    for(int i=0;i<n;i++)
    {
        while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--)
    {
        while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    if(n>1) m--;
    return m;
}
int dcmp(double val)
{
    if(abs(val)<EPS) return 0;
    else if(val>0) return 1;
    else return -1;
}
bool isPointOnSegment(Point p,Point a,Point b)//点在线段上(不包括端点)
{
    return cross(a-p,b-p)==0&&dot(a-p,b-p)<0;
}
bool segmentInterect(Point a1,Point a2,Point b1,Point b2)//规范相交
{
    int c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1);
    int c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
int isPointInPolygon(Point *ch,int n,Point p)//是否在多边形内部
{
    int wn=0;
    for(int i=0;i<n;i++)
    {
        if(isPointOnSegment(p,ch[i],ch[(i+1)%n])) return 1;
        int k=dcmp(cross(ch[(i+1)%n]-ch[i],p-ch[i]));
        int d1=dcmp(ch[i].y-p.y);
        int d2=dcmp(ch[(i+1)%n].y-p.y);
        if(k>0&&d1<=0&&d2>0) wn++;
        if(k<0&&d2<=0&&d1>0) wn--;
    }
    if(wn) return 1;
    else return 0;
}
int main()
{
    int n,m,bct,wct;
    while(scanf("%d%d",&n,&m)!=EOF,n+m)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&white[i].x,&white[i].y);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%lf%lf",&black[i].x,&black[i].y);
        }
        wct=convexHull(white,n,wout);
        bct=convexHull(black,m,bout);
        bool flag=false;
        for(int i=0;i<wct;i++)
        {
            if(isPointInPolygon(bout,bct,wout[i]))
            {
                flag=true;
                break;
            }
        }
        if(!flag)
        {
            for(int i=0;i<bct;i++)
            {
                if(isPointInPolygon(wout,wct,bout[i]))
                {
                    flag=true;
                    break;
                }
            }
        }
        if(!flag)
        {
            for(int i=0;i<wct;i++)
            {
                if(flag) break;
                for(int j=0;j<bct;j++)
                {
                    if(segmentInterect(wout[i],wout[(i+1)%wct],bout[j],bout[(j+1)%bct]))
                    {
                        flag=true;
                        break;
                    }
                }
            }
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

B - Shape of HDU
题意：
给定多边形的逆序节点，判断一个多边形是不是凸多边形
题解：
可以用相邻两边的旋转角来判断，逆时针取点，若存在点p1, p2, p3，矢边p1p2, 到p2p3，为顺时针旋转则此多边形为凹多边形,可以用叉积判断时针方向

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=50000;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
};
Point point[MAXN];
typedef Point Vector;
Vector operator +(Vector A,Vector B)
{
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF,n)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&point[i].x,&point[i].y);
        }
        bool flag=true;
        for(int i=0;i<n-2;i++)
        {
            if(cross(point[i+1]-point[i],point[i+2]-point[i])<0)
            {
                flag=false;
                break;
            }
        }
        if(cross(point[n-1]-point[n-2],point[0]-point[n-1])<0) flag=false;
        if(cross(point[0]-point[n-1],point[1]-point[0])<0) flag=false;
        if(flag) printf("convex\n");
        else printf("concave\n");
    }
}

C - Surround the Trees
题意：
求凸包周长
题解：
这里比较坑的地方有，1个点的时候输出０，两个点的时候，凸包求出来是有两条边的，但是只需输出两点距离即可

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=110;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
};
Point in[MAXN],out[MAXN];
typedef Point Vector;
Vector operator +(Vector A,Vector B)
{
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator -(Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
bool operator <(const Point &a,const Point &b)
{
    return a.x<b.x||(a.x==b.x&&(a.y<b.y));
}
int convexHull(Point *p,int n,Point *ch)
{
    sort(p,p+n);
    int m=0;
    for(int i=0;i<n;i++)
    {
        while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--)
    {
        while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    if(n>1) m--;
    return m;
}
double length(Vector A)
{
    return sqrt(A.x*A.x+A.y*A.y);
}
double perimeter(Point *p,int n)
{
    double len=0;
    for(int i=0;i<n-1;i++)
    {
        len+=length(p[i+1]-p[i]);
    }
    len+=length(p[0]-p[n-1]);
    return len;
}
int main()
{
    int n,ans;
    double len;
    while(scanf("%d",&n)!=EOF,n)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&in[i].x,&in[i].y);
        }
        if(n==1)
        {
            printf("0.00\n");
            continue;
        }
        else if(n==2)
        {
            printf("%.2f\n",length(in[1]-in[0]));
            continue;
        }
        ans=convexHull(in,n,out);
        len=perimeter(out,ans);
        printf("%.2f\n",len);
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,657评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,662评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,143评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,732评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,837评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,036评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,126评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,868评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,315评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,641评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,773评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,470评论 4赞 333
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,126评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,859评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,095评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,584评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,676评论 2赞 351

推荐阅读更多精彩内容

  • 稳定凸包
    转载自这里 稳定的凸包: 比如有4个点： 这四个点是某个凸包上的部分点，他们连起来后确实还是一个凸包。但是原始的凸...
    Gitfan阅读 680评论 0赞 0
  • 寻找最大凸多边形
    某公司今年的技能鉴定考试是这样的： 给出一系列平面直角坐标系中的点的坐标，写一个程序，找出能够围住这些点的最大的凸...
    雷雨后阅读 8,521评论 3赞 10
  • 凸包：Graham's Scan
    1.概念 凸包(Convex Hull)是一个计算几何（图形学）中的概念。用不严谨的话来讲，给定二维平面上的点集，...
    三三de酒阅读 3,885评论 0赞 1
  • 半平面交
    具体步骤看训练指南 ( 一 )求解半平面交 Uyuw's Concert 类似的题目：hdu 1632 Polyg...
    Gitfan阅读 567评论 0赞 0
  • 多边形的偏移填充算法
    前言 多边形偏移 (polygon offset) 算法可能我们印象不深，不过用过 autoCAD 的同学应该有印...
    zyl06阅读 11,317评论 19赞 14