题目链接: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;、

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

代码:

 #include <iostream>
#include <stdio.h>
#define MAXN 1000001
using namespace std; int a[MAXN], b[MAXN]; int gg(int p1, int p2, int p3){
int jj=(a[p2]-a[p1])*(b[p3]-b[p2])-(a[p3]-a[p2])*(b[p2]-b[p1]);
return jj<?:;
} int main(void){
int n;
while(scanf("%d", &n)&&n){
for(int i=; i<n; i++){
scanf("%d%d", &a[i], &b[i]);
}
int flag=;
a[n]=a[], b[n]=b[]; //***注意第n-1个点的判断
a[n+]=a[], b[n+]=b[];
for(int i=; i<n; i++){
flag=gg(i, i+, i+);
if(!flag){
printf("concave\n");
break;
}
}
if(!flag){
continue;
}
printf("convex\n");
}
return ;
}

最新文章

  1. 代码管理工具 --- git的学习笔记二《git的工作原理》
  2. ListView中动态显示和隐藏Header&amp;Footer
  3. http协议状态码对照表
  4. [NodeJS] Deploy a Node Application with the Now CLI
  5. ADO.NET的五个主要对象
  6. python基础知识(引用)
  7. Java基础知识强化之集合框架笔记55:Map集合之HashMap集合(HashMap&lt;Integer,String&gt;)的案例
  8. Python中classmethod与staticmethod区别
  9. JAVA责任链设计模式
  10. Java 重入锁 ReentrantLock
  11. 【NumberValidators】大陆身份证验证
  12. [Swift]LeetCode804. 唯一摩尔斯密码词 | Unique Morse Code Words
  13. 部分安卓机型1px边框无法显示解决方法
  14. Ubuntu创建新用户的正确姿势
  15. 158A Next Round
  16. MHL技术剖析,比HDMI更强【转】
  17. sublime text 3配置c/c++编译环境
  18. JVM G1GC参数配置
  19. 如何添加查找 ng vue 客户端快捷方式
  20. STL 优先队列详解

热门文章

  1. EntityFramework之摸索EF底层(八)
  2. tyvj1938 最优战舰
  3. Myeclipse中添加XFire插件支持
  4. HDU 4497 GCD and LCM (数学,质数分解)
  5. POJ 3922A Simple Stone Game
  6. Java对象相关元素的初始化过程
  7. 阿里云数加平台——BI报表使用概述和总结
  8. Animation 的setFillAfter
  9. poj2828 Buy ticket
  10. MySQL 笔记整理(2) --日志系统,一条SQL查询语句如何执行
  11. vue教学视频(小程序教学视频)
  12. struts基础3-把数据写入页面
  13. mysql基本操作(二)
  14. Runtime之方法
  15. CentOS 6 安装配置JDK+tomcat环境
  16. Windows下安装Python及Eclipse中配置PyDev插件
  17. 《JAVA---day03---运算符》
  18. Concurrency Managed Workqueue(三)创建workqueue代码分析
  19. linux mint 19 与windows时间不同步
  20. PHPStorm/webstorm/PyCharm tips