寒假作业，shape of HDU-白红宇

寒假作业，shape of HDU

阅读量：5844 次

发布时间：2019-06-18

本文共 1265 字，大约阅读时间需要 4 分钟。

这道题的话，我拿到题是有点懵圈的，如果要我自己判断的话，我也要自己在纸上建立坐标轴然后一一将点标出，后用肉眼判断。这个用代码实现嘛……

后来就只能参考大神们的算法啦。

判断方法：

向量a=(x1,y1),b=(x2,y2)；

向量的叉积a×b=x1*y2-x2*y1; 当a×b>0时，b在a的逆时针方向，当a×b=0时，b与a共线，当a×b<0时，b在a的顺时针方向。

对于连续输入的三点A(x1,y1)，B(x2,y2)，C(x3,y3)；

根据凸多边形的性质：向量AC(x3-x1,y3-y1)必定在向量AB(x2-x1,y2-y1)的逆时针方向,或者共线。

所以AB×AC>=0，即ans=(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)>=0。当出现ans<0时，即为凹多边形。

该题要判断所有点吗，如果只要有个点不成立，那么该多边形就是凹变形。如果该多边形要是凸变形，那所有的点都要成立。

源地址：http://blog.csdn.net/wangkemingshishuaige/article/details/47658267

太强了。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              11 #include 
               
                12 #include 
                
                 13 #include
                 
                  14 #include
                  
                   15 using namespace std;16 typedef long long ll;17 #define pi 3.1415926535897932384626433832718 #define E 2.7182818284619 #define INF 0x3f3f3f3f20 #define maxn 55555521 struct node22 {23 int x, y;24 }p[11000];25 bool judge(int x1, int y1, int x2, int y2, int x3, int y3)26 {27 return (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1) >= 0;28 }29 int main()30 {31 int n, i, flage;32 while (scanf("%d", &n) != EOF&&n != 0)33 {34 flage = 0;35 for (i = 0; i

转载于:https://www.cnblogs.com/ineedyou/p/8469771.html

你可能感兴趣的文章