精华内容
下载资源
问答
  • 判断凸多边形

    2013-08-10 15:37:00
    凸多边形 boolean tag = true ; int j,k,t; for ( int i=0; i; i++ ) { // k,t直接对n求余就行了 j = i; k = i+1 ; t = i+2 ; // 以三角形为例看看 if (k== n) { k = 0 ; } if (t==n+...
            以HDU2108为例,去AC吧。
    
    //点逆序输入
    import java.util.Scanner;
    //1s
    public class HDU2108 {
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
          int x,y;
          int n = sc.nextInt();
          if(0==n) {
            break;
          }
          Point[] p = new Point[n];
          for(int i=0; i<n; i++) {
            p[i] = new Point();
          }
          for(int i=0; i<n; i++) {
            x = sc.nextInt();
            y = sc.nextInt();
            p[i] = new Point(x,y);
          }
          //凸多边形
          boolean tag = true;
          int j,k,t;
          for(int i=0; i<n; i++) {
            //k,t直接对n求余就行了
            j = i;
            k = i+1;
            t = i+2;
            //以三角形为例看看
            if(k==n) {
              k = 0;
            }
            if(t==n+1) {
              t = 1;
            }
            if(t==n) {
              t = 0;
            }
            //注意是后面减去前面的
            Point p1 = new Point(p[k].x - p[j].x,
                p[k].y - p[j].y);
            Point p2 = new Point(p[t].x - p[k].x,
                p[t].y - p[k].y);
            //叉积
            int ans = p1.x*p2.y - p1.y*p2.x;
            if(ans<0) {
              tag = false;
              break;
            }
          }
          if(tag) {
            System.out.println("convex");
          }else {
            System.out.println("concave");
          }
        }
      }
    }
    class Point {
      int x;
      int y;
      public Point() {
        this.x = 0;
        this.y = 0;
      }
      public Point(int x, int y) {
        this.x = x;
        this.y = y;
      }
    }
    展开全文
  • 本文提供了使用JAVA判断凸多边形的示例代码供大家参考学习,需要的朋友可以看一下
  • hdu2108(判断凸多边形)

    2016-11-17 19:24:00
    判断凸多边形的方法比较多,如:若存在一条边,它的两边都有点,那么它是凹多边形;若存在一个点,去掉它后该多边形的面积大于原来的多边形,则它是凹多边形; 我们还可以用相邻两边的旋转角来判断,逆时针取点,若...

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2108

     

    题意:

    给出一个多边形的所有顶点,判断是不是凸多边形;

     

    思路:

    判断凸多边形的方法比较多,如:若存在一条边,它的两边都有点,那么它是凹多边形;若存在一个点,去掉它后该多边形的面积大于原来的多边形,则它是凹多边形;

    我们还可以用相邻两边的旋转角来判断,逆时针取点,若存在点p1, p2, p3,矢边p1p2, 到p2p3,为顺时针旋转则此多边形为凹多边形;

    对于判断旋转角,我们可以用矢量乘积来判断:

    令 gg=p1p2*p2p3;

    若gg<0, 其旋转为顺时针;

    若gg=0, 两边共线;

    若gg>0, 其旋转为逆时针;

    对于如何计算二维向量的叉积,我们可以将其纵坐标看做0,再像计算三维向量叉积那样用行列式计算;

    p1p2*p2p3=x1*y2-x2*y1;、

    此方法代码比较简洁,时间复杂度也较小,我们就选这个方法啦;

     

    代码:

     1 #include <iostream>
     2 #include <stdio.h>
     3 #define MAXN 1000001
     4 using namespace std;
     5 
     6 int a[MAXN], b[MAXN];
     7 
     8 int gg(int p1, int p2, int p3){
     9     int jj=(a[p2]-a[p1])*(b[p3]-b[p2])-(a[p3]-a[p2])*(b[p2]-b[p1]);
    10     return jj<0?0:1;
    11 }
    12 
    13 int main(void){
    14     int n;
    15     while(scanf("%d", &n)&&n){
    16         for(int i=0; i<n; i++){
    17             scanf("%d%d", &a[i], &b[i]);
    18         }
    19         int flag=1;
    20         a[n]=a[0], b[n]=b[0]; //***注意第n-1个点的判断
    21         a[n+1]=a[1], b[n+1]=b[1];
    22         for(int i=0; i<n; i++){
    23             flag=gg(i, i+1, i+2);
    24             if(!flag){
    25                 printf("concave\n");
    26                 break;
    27             }
    28         }
    29         if(!flag){
    30             continue;
    31         }
    32         printf("convex\n");
    33     }
    34     return 0;
    35 }

     

    转载于:https://www.cnblogs.com/geloutingyu/p/6075145.html

    展开全文
  • 分析:判断凸多边形可以使用相邻的三个点叉积判断,因为不知道顺时针还是逆时针,所以叉积如果有有整数和负数,那么一定不是凸多边形(注意允许多多点在一条线段上)。判断圆在凸多边形首先要判断圆心是否在多边形内...
    题目大意:首先给一个圆的半径和圆心,然后给一个多边形的所有点(多边形按照顺时针或者逆时针给的),求,这个多边形是否是凸多边形,如果是凸多边形在判断这个圆是否在这个凸多边形内。
     
    分析:判断凸多边形可以使用相邻的三个点叉积判断,因为不知道顺时针还是逆时针,所以叉积如果有有整数和负数,那么一定不是凸多边形(注意允许多多点在一条线段上)。判断圆在凸多边形首先要判断圆心是否在多边形内,如果在多边形内,再次判断圆心到达到变形每条边的最短距离,如果小于半径就是不合法。ps:一道好题,通过这个题学会了不少东西。
     
    代码如下:
    =======================================================================================================================================
    #include<stdio.h>
    #include<math.h>
    #include<algorithm>
    using namespace std;
    
    const int MAXN = 1e3+7;
    const double EPS = 1e-8;
    const double oo = 1e10+7;
    
    struct Point
    {
        double x, y;
        Point(double x=0, double y=0):x(x),y(y){}
        Point operator - (const Point &tmp)const{
            return Point(x-tmp.x, y-tmp.y);
        }
        double operator ^(const Point &tmp)const{
            return x*tmp.y - y*tmp.x;
        }
        double operator *(const Point &tmp)const{
            return x*tmp.x + y*tmp.y;
        }
    };
    double Dist(Point a, Point b)
    {///两点间的距离
        return sqrt((a-b)*(a-b));
    }
    int Sign(double t)
    {
        if(t > EPS)return 1;
        if(fabs(t) < EPS)return 0;
        return -1;///负数
    }
    struct Segment
    {
        Point S, E;
        Segment(Point S=0, Point E=0):S(S), E(E){}
        bool OnSeg(const Point &p)
        {///点是否在线段上
            if(Sign( (S-E)^(p-E) ) == 0)///共线
            if(Sign( (p.x-S.x)*(p.x-E.x) ) <= 0)///位于线段的中间或者端点
            if(Sign( (p.y-S.y)*(p.y-E.y) ) <= 0)
                return true;
            return false;
        }
        bool Inter(const Segment &tmp)
        {///只考虑完全相交的情况
            return Sign((S-E)^(tmp.S-E)) * Sign((S-E)^(tmp.E-E)) == -1;
        }
        Point NearPoint(const Point &p)
        {///点到线段最近的点
            Point res;
            double r = ((E-S)*(p-S)) / ((E-S)*(E-S));
    
            if(r > EPS && (1.0 - r) > EPS )
            {///点在线段的投影在线段上
                res.x = S.x + r * (E.x-S.x);
                res.y = S.y + r * (E.y-S.y);
            }
            else
            {///求离最近的端点
                if(Dist(p, S) < Dist(p, E))
                    res = S;
                else
                    res = E;
            }
    
            return res;
        }
    };
    struct Poly
    {
        int N;
        Point vertex[MAXN];
    
        bool IsConvex()
        {///判断是否是凸多边形,可以共线
            int vis[3] = {0};
            for(int i=0; i<N; i++)
            {///如果同时出现整数和负数,说明存在凹的
                int k = Sign((vertex[(i+1)%N]-vertex[i])^(vertex[(i+2)%N]-vertex[i]));
                vis[k+1] = 1;
    
                if(vis[0] && vis[2])
                    return false;
            }
            return true;
        }
        int InPoly(const Point &Q)
        {///判断点Q是否在多边形内,射线法,奇数在内,偶数在外
        ///在圆上返回0, 圆外-1, 圆内 1
            Segment ray(Point(-oo, Q.y), Q);///构造射线的最远处
            int cnt=0;///统计相交的边数
    
            for(int i=0; i<N; i++)
            {
                Segment edge(vertex[i], vertex[(i+1)%N]);
    
                if(edge.OnSeg(Q) == true)
                    return 0;///点在边上
    
                if(ray.OnSeg(vertex[i]) == true)
                {///如果相交连接点,那么取y值小的点
                    if(vertex[(i+1)%N].y - vertex[i].y > EPS)
                        cnt++;
                }
                else if(ray.OnSeg(vertex[(i+1)%N]) == true)
                {
                    if(vertex[i].y - vertex[(i+1)%N].y > EPS)
                        cnt++;
                }
                else if(ray.Inter(edge) && edge.Inter(ray))
                    cnt++;
            }
    
            if(cnt % 2)
                return 1;
            else
                return -1;
        }
    };
    struct Circle
    {
        Point center;///圆心
        double R;///半径
    };
    
    bool Find(Poly &a, Circle &c)
    {///判断圆是否在多边形内
        if(a.InPoly(c.center) == -1)
            return false;///如果圆心在多边形外面
    
        for(int i=0; i<a.N; i++)
        {
            Segment edge(a.vertex[i], a.vertex[(i+1)%a.N]);
            double len = Dist(c.center, edge.NearPoint(c.center));
    
            if(Sign(len-c.R) < 0)
                return false;
        }
    
        return true;
    }
    
    int main()
    {
        Poly a;///定义多边形
        Circle c;///定义圆
    
        while(scanf("%d", &a.N) != EOF && a.N > 2)
        {
            scanf("%lf%lf%lf", &c.R, &c.center.x, &c.center.y);
            for(int i=0; i<a.N; i++)
                scanf("%lf%lf", &a.vertex[i].x, &a.vertex[i].y);
    
            if(a.IsConvex() == false)
                printf("HOLE IS ILL-FORMED\n");
            else if(Find(a, c) == false)
                printf("PEG WILL NOT FIT\n");
            else
                printf("PEG WILL FIT\n");
        }
    
        return 0;
    }

     

    转载于:https://www.cnblogs.com/liuxin13/p/4799667.html

    展开全文
  • 首先判断是不是凸多边形 然后判断圆是否在凸多边形内 ...POJ 1584 A Round Peg in a Ground Hole(判断凸多边形,点到线段距离,点在多边形内) #include <iostream> #include <cstdio> #include ...

    首先判断是不是凸多边形

    然后判断圆是否在凸多边形内

    不知道给出的点是顺时针还是逆时针,所以用判断是否在多边形内的模板,不用是否在凸多边形内的模板

    POJ 1584 A Round Peg in a Ground Hole(判断凸多边形,点到线段距离,点在多边形内)

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    const double eps=1e-8;
    const double PI = acos(-1.0);
    
    int sgn(double x)
    {
        if(fabs(x) < eps) return 0;
        return x < 0 ? -1: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;
        }
        //点积
        double operator *(const Point &b)const
        {
            return x*b.x + y*b.y;
        }
        void input()
        {
            scanf("%lf%lf",&x,&y);
        }
    };
    
    struct Line
    {
        Point p,q;
        Line() {};
        Line(Point _p,Point _q)
        {
            p = _p,q = _q;
        }
    };
    
    //*两点间距离
    double dist(Point a,Point b)
    {
        return sqrt((a-b)*(a-b));
    }
    
    //*判断凸多边形
    //允许共线边
    //点可以是顺时针给出也可以是逆时针给出
    //点的编号0~n-1
    bool isconvex(Point poly[],int n)
    {
        bool s[3];
        memset(s,false,sizeof(s));
        for(int i = 0; i < n; i++)
        {
            s[sgn( (poly[(i+1)%n]-poly[i])^(poly[(i+2)%n]-poly[i]) )+1] = true;
            if(s[0] && s[2])return false;
        }
        return true;
    }
    
    //*点到线段的距离
    //返回点到线段最近的点
    Point NearestPointToLineSeg(Point P,Line L)
    {
        Point result;
        double t = ((P-L.p)*(L.q-L.p))/((L.q-L.p)*(L.q-L.p));
        if(t >= 0 && t <= 1)
        {
            result.x = L.p.x + (L.q.x - L.p.x)*t;
            result.y = L.p.y + (L.q.y - L.p.y)*t;
        }
        else
        {
            result = dist(P,L.p) < dist(P,L.q)? L.p:L.q;
        }
        return result;
    }
    
    //*判断点在线段上
    bool OnSeg(Point P,Line L)
    {
        return
            sgn((L.p-P)^(L.q-P)) == 0 &&
            sgn((P.x - L.p.x) * (P.x - L.q.x)) <= 0 &&
            sgn((P.y - L.p.y) * (P.y - L.q.y)) <= 0;
    }
    
    //*判断点在凸多边形内
    //点形成一个凸包,而且按逆时针排序(如果是顺时针把里面的<0改为>0)
    //点的编号:0~n-1
    //返回值:
    //-1:点在凸多边形外
    //0:点在凸多边形边界上
    //1:点在凸多边形内
    int inConvexPoly(Point a,Point p[],int n)
    {
        for(int i = 0; i < n; i++)
        {
            if(sgn((p[i]-a)^(p[(i+1)%n]-a)) < 0)return -1;
            else if(OnSeg(a,Line(p[i],p[(i+1)%n])))return 0;
        }
        return 1;
    }
    
    //*判断线段相交
    bool inter(Line l1,Line l2)
    {
        return
            max(l1.p.x,l1.q.x) >= min(l2.p.x,l2.q.x) &&
            max(l2.p.x,l2.q.x) >= min(l1.p.x,l1.q.x) &&
            max(l1.p.y,l1.q.y) >= min(l2.p.y,l2.q.y) &&
            max(l2.p.y,l2.q.y) >= min(l1.p.y,l1.q.y) &&
            sgn((l2.p-l1.q)^(l1.p-l1.q))*sgn((l2.q-l1.q)^(l1.p-l1.q)) <= 0 &&
            sgn((l1.p-l2.q)^(l2.p-l2.q))*sgn((l1.q-l2.q)^(l2.p-l2.q)) <= 0;
    }
    
    //*判断点在任意多边形内
    //射线法,poly[]的顶点数要大于等于3,点的编号0~n-1
    //返回值
    //-1:点在多边形外
    //0:点在多边形边界上
    //1:点在多边形内
    int inPoly(Point p,Point poly[],int n)
    {
        int cnt;
        Line ray,side;
        cnt = 0;
        ray.p = p;
        ray.q.y = p.y;
        ray.q.x = -100000000000.0;//-INF,注意取值防止越界
        for(int i = 0; i < n; i++)
        {
            side.p = poly[i];
            side.q = poly[(i+1)%n];
            if(OnSeg(p,side))return 0;
            //如果平行轴则不考虑
            if(sgn(side.p.y - side.q.y) == 0)
                continue;
            if(OnSeg(side.p,ray))
            {
                if(sgn(side.p.y - side.q.y) > 0)cnt++;
            }
            else if(OnSeg(side.q,ray))
            {
                if(sgn(side.q.y - side.p.y) > 0)cnt++;
            }
            else if(inter(ray,side)) cnt++;
        }
        return cnt % 2 ? 1:-1;
    }
    
    Point pot[105],peg;
    double rad;
    
    int main()
    {
    //    freopen("in.txt","r",stdin);
        int n;
        while(~scanf("%d",&n))
        {
            if(n<3) break;
            scanf("%lf",&rad);
            peg.input();
            for(int i=0;i<n;i++)
                pot[i].input();
            if(!isconvex(pot,n))
            {
                puts("HOLE IS ILL-FORMED");
                continue;
            }
            if(inPoly(peg,pot,n)<0)
            {
                puts("PEG WILL NOT FIT");
                continue;
            }
            bool flag=true;
            for(int i=0;i<n-1;i++)
            {
                if( sgn(dist(peg,NearestPointToLineSeg(peg,Line(pot[i],pot[(i+1)%n])))-rad)<0 )
                {
                    flag=false;
                    break;
                }
            }
            puts(flag? "PEG WILL FIT":"PEG WILL NOT FIT");
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/pach/p/7220537.html

    展开全文
  • HDU-2108 Shape of HDU判断凸多边形(叉积) xzc 2019.5.21 HDU题目链接<- 题意:   给出n边形按逆时针排好序的n个顶点,判断是否是凸多边形 Sample input 4 0 0 1 0 1 1 0 1 0 Sample output convex 叉积的...
  • } //凸多边形 boolean tag = true; int j,k,t; for(int i=0; i //k,t直接对n求余就行了 j = i; k = i+1; t = i+2; //以三角形为例看看 if(k==n) { k = 0; } if(t==n+1) { t = 1; } if(t==n) { t = 0; } //注意是...
  • 题目大意: 给定n个点,但是不确定是顺时针还是逆时针的,判断它是否是凸多边形,如果是凸度变形的话,题目给定了一个圆心和半径,让求圆是否在凸多边形内。 关键步骤:  1. 判断是否为凸多边形  2. 如果是...
  • 2 几何+判断凸多边形 3 */ 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<iostream> 9 #incl...
  • POJ 1584 A Round Peg in a Ground Hole(判断凸多边形,点到线段距离,点在多边形内) A Round Peg in a Ground Hole Time Limit: 1000MS   Memory Limit: 10000K Total Submissions:...
  • 按照逆时针顺序,输入n个点,判断给出的图形是凸多边形,还是凹多边形。 a x b = | a | * | b | * sin (ab) 叉积的应用,观察两种多边形的特点可以看出,凹多边形因为有一部分凹进去,所以,相邻边的叉积会...
  • 判断凸多边形并排序算法

    千次阅读 2016-04-17 23:01:34
    在平面直角坐标系中,给定一个点序列,判断这些点是否能够构成凸多边形, 并且按照顺时针方向输出这些点。 其他要求: 1.输出的起始的为距离原点最近的点,如果多点距离原点相等,取其中任一点即可; 2.如果有...
  • 大致题意: 按照顺时针或逆时针方向输入一个n边形的顶点坐标集,先判断这个n边形是否为凸包。 再给定一个圆形(圆心坐标和半径),判断这个圆是否完全在n变形内部。...注意输入完顶点集后,要封闭多边形,方便后面
  • HDOJ2108 判断凸多边形

    2017-08-26 15:16:34
    政府划拨的这块用地是一个多边形,为了描述它,我们用逆时针方向的顶点序列来表示,我们很想了解这块地的基本情况,现在请你编程判断HDU的用地是凸多边形还是凹多边形呢?   Input 输入包含多...
  • 政府划拨的这块用地是一个多边形,为了描述它,我们用逆时针方向的顶点序列来表示,我们很想了解这块地的基本情况,现在请你编程判断HDU的用地是凸多边形还是凹多边形呢?     Input 输入包含多组测试数据...
  • 判断是否为凸多边形,可以用叉积来判断,如果一个多边形上存在连续的三条边,l1,l2,l3(方向得是一致的,都是顺时针或者都是逆时针),(l1 X l2) *(l2 X l3)的值为负,那么这个多边形就是凹多边形,否则就为...
  • 思路:先判断该多边形是否是凸多边形,由于给出多边形的坐标可能是顺时针方向也可能是逆时针方向,所以判断时分两种情况,如果是凸多边形,在判断该圆的圆心是否在多边形内部,这也可以用叉乘来判断,最后判断圆心到...
  • 我们知道三个点可以确定两个向量,那么我们按照题意的顺序依次取三个点(a,b,c)组成...这时我们发现叉积小于零时组成的形状是凹的,那么这个题判断是否有三个点叉积小于零即可。 #include <iostream> #inc...
  • Shape of HDU Problem Description 话说上回讲到海东集团推选老总的事情,最终...政府划拨的这块用地是一个多边形,为了描述它,我们用逆时针方向的顶点序列来表示,我们很想了解这块地的基本情况,现在请你编程判断HDU
  • 题意:给出一个多边形和一个圆,问是否是凸多边形,若是则再问圆是否在凸多边形内部。 5 1.5 1.5 2.0 1.0 1.0 2.0 2.0 1.75 2.0 1.0 3.0 0.0 2.0 5 1.5 1.5 2.0 1.0 1.0 2.0 2.0 1.75 2.5 1.0 3.0
  • 题意 按照顺时针或逆时针方向输入一个n边形的顶点坐标集,先判断这个n边形是否为凸包。...2.判断圆包含在凸多边形中:一定要保证圆心在凸多边形里面。然后判断圆心到每条线段的距离要大于等于半径。。 #incl...
  • 政府划拨的这块用地是一个多边形,为了描述它,我们用逆时针方向的顶点序列来表示,我们很想了解这块地的基本情况,现在请你编程判断HDU的用地是凸多边形还是凹多边形呢?   Input 输入包含多组测试...
  • 即第0个点等于第n个点,第n+1个点等于第1个点),然后如果是凸多边形的,就判断点是否在多边形内,因为多边形是凸的,这一步也就简单了许多,直接枚举相邻的两条边,两条边之间的点与圆心构成一条直线L,判断这两条...
  • 政府划拨的这块用地是一个多边形,为了描述它,我们用逆时针方向的顶点序列来表示,我们很想了解这块地的基本情况,现在请你编程判断HDU的用地是凸多边形还是凹多边形呢?   Input 输入包含多组测试...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 624
精华内容 249
关键字:

判断凸多边形