题目链接:https://vjudge.net/problem/POJ-3348

题意:转换题意后即是求凸包的面积。

思路:

  套模板,求凸包面积即转换为多个三角形面积之和,用叉积求,然后除2,因为本题除50,所以最后除100。

AC code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std; const int maxn=;
const double PI=acos(-1.0); struct Point{
int x,y;
Point():x(),y(){}
Point(int x,int y):x(x),y(y){}
}list[maxn];
int stack[maxn],top; //计算叉积p0p1×p0p2
int cross(Point p0,Point p1,Point p2){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//计算p1p2的距离
double dis(Point p1,Point p2){
return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
//极角排序函数,角度相同则距离小的在前面
bool cmp(Point p1,Point p2){
int tmp=cross(list[],p1,p2);
if(tmp>) return true;
else if(tmp==&&dis(list[],p1)<dis(list[],p2)) return true;
else return false;
}
//输入,把最左下角放在list[0],并且进行极角排序
void init(int n){
Point p0;
scanf("%d%d",&list[].x,&list[].y);
p0.x=list[].x;
p0.y=list[].y;
int k=;
for(int i=;i<n;++i){
scanf("%d%d",&list[i].x,&list[i].y);
if((p0.y>list[i].y)||((p0.y==list[i].y)&&(p0.x>list[i].x))){
p0.x=list[i].x;
p0.y=list[i].y;
k=i;
}
}
list[k]=list[];
list[]=p0;
sort(list+,list+n,cmp);
}
//graham扫描法求凸包,凸包顶点存在stack栈中
//从栈底到栈顶一次是逆时针方向排列的
//如果要求凸包的一条边有2个以上的点
//那么要将while中的<=改成<
//但这不能将最后一条边上的多个点保留
//因为排序时将距离近的点排在前面
//那么最后一条边上的点仅有距离最远的会被保留,其余的会被出栈
//所以最后一条边需要特判
void graham(int n){
if(n==){
top=;
stack[]=;
return;
}
top=;
stack[]=;
stack[]=;
for(int i=;i<n;++i){
while(top>&&cross(list[stack[top-]],list[stack[top]],list[i])<=) --top;
stack[++top]=i;
}
} int n,ans; int main(){
while(~scanf("%d",&n)){
ans=;
init(n);
graham(n);
for(int i=;i<top;++i)
ans+=cross(Point(,),list[stack[i]],list[stack[i+]]);
ans+=cross(Point(,),list[stack[top]],list[stack[]]);
printf("%d\n",ans/);
}
return ;
}

最新文章

  1. iOS开发——高级篇——iPad开发、iPad开发中的modal
  2. PL/Proxy介绍
  3. RMQ之ST算法模板
  4. html中设置锚点定位的几种常见方法(#号定位)
  5. 学习K&amp;R时初学者经常遇到的一个问题——EOF
  6. Android JNI学习之javah命令的正确使用(找了好半天才找到的,汉,网上好多说法都没用)
  7. openSUSE13.1无法打开Yast的安装/移除软件管理软件的解决办法&#183;(未解决,临时方法) 收获:有问题,读日志
  8. 使用Intellij IDEA从零使用Spring MVC
  9. tengine+lua的安装步骤
  10. ASP.NET多次点击提交按钮以及Session超时和丢失过期问题
  11. php对提交数据的验证
  12. iOS实用的小技巧
  13. 自定义filter包
  14. Java导出excel并下载功能
  15. VS2008下WinRar源码生成dll和 lib总结
  16. Objective-C KVC 自己主动转换类型研究
  17. IT段子,娱乐一下
  18. C语言面试问答(3)
  19. 详解Objective-C的meta-class 分类: ios相关 ios技术 2015-03-07 15:41 51人阅读 评论(0) 收藏
  20. 通过Canvas及File API缩放并上传图片

热门文章

  1. 【CSP模拟赛】仔细的检查(树的重心&amp;树hash)
  2. fluent提供的边界条件解析【转载】
  3. Gremlin入门
  4. linux10.日志服务器建立和克隆机的网卡问题
  5. 第2课第1节_Java面向对象编程_类的引入_P【学习笔记】
  6. 表观 | Enhancer | ChIP-seq | 转录因子 | 数据库专题
  7. Java 泛型 (Generics)
  8. 阿里云ECS服务器环境搭建(1) —— ubuntu 16.04 图形界面的安装
  9. EnvironmentError: mysql_config not found
  10. Linux安装Windows字体