hdu2108(判断凸多边形)
2024-08-24 07:52:21
题目链接: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 ;
}
最新文章
- 【转】BAT 批处理脚本 教程
- Python自动化 【第十五篇】:CSS、JavaScript 和 Dom介绍
- 使用Spring Security Oauth2完成RESTful服务password认证的过程
- NBOJv2 1004 蛤玮打扫教室(线段树区间更新区间最值查询)
- 循环语句while与for的穷举迭代
- 设计模式 ( 十八 ) 策略模式Strategy(对象行为型)
- 【转】关于Xcode的Other Linker Flags
- .NET垃圾回收机制 转
- 跨服务器的sql使用
- IDEA配置Tomcat
- Myeclipse Db Browser使用
- 修改css的(屏蔽)overflow: hidden;实现浏览器能把网页全图保存成图片
- 如何调用别人提供的API?
- SQL 创建联合主键Table
- OC语言-runtime
- 百度前端学院task33源码及总结——听指令的小方块
- LeetCode题解之Remove Nth Node From End of List
- Libre 6009 「网络流 24 题」软件补丁 / Luogu 2761 软件安装问题 (最短路径,位运算)
- Java 和 JSP 实现网站访问量统计 (刷新过滤)
- BZOJ4589: Hard Nim(FWT 快速幂)
热门文章
- HDU HDU1558 Segment set(并查集+判断线段相交)
- [转载]Jquery mobile 新手问题总汇
- word20161129
- 跟着百度学PHP[4]OOP面对对象编程-15-魔术方法__call方法
- linux下VMware安装出现的问题解决
- ubuntu查找软件包
- How can I determine the URL that a local Git repository was originally cloned from?
- [20160804]synchronized
- block,inline和inline-block对比
- http://www.htmleaf.com/ziliaoku/qianduanjiaocheng/