题目大意:

给定的n个点 能圈出的最大范围中

若每50平方米放一头牛 一共能放多少头

求凸包 答案就是 凸包的面积/50 向下取整

/// 求多边形面积
// 凹多边形同样适用 因为点积求出的是有向面积
double areaPg()
{
double res=;
for(int i=;i<k-;i++) // 以t[0]为划分顶点
res+=(t[i]-t[]).det(t[i+]-t[]);
return res/2.0;
}
#include <cstdio>
#include <algorithm>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std; const double eps=1e-;
double add(double a,double b) {
if(abs(a+b)<eps*(abs(a)+abs(b))) return ;
return a+b;
}
struct P {
double x,y;
P(){};
P(double _x,double _y):x(_x),y(_y){};
P operator - (P p) {
return P(add(x,-p.x),add(y,-p.y)); }
P operator + (P p) {
return P(add(x,p.x),add(y,p.y)); }
P operator * (double d) {
return P(x*d,y*d); }
double dot(P p) {
return add(x*p.x,y*p.y); }
double det(P p) {
return add(x*p.y,-y*p.x); }
}p[], t[];
int n, k;
bool cmp(P a,P b) {
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
void andrew()
{
sort(p,p+n,cmp);
k=;
for(int i=;i<n;i++) {
while(k> && (t[k-]-t[k-]).det(p[i]-t[k-])<)
k--;
t[k++]=p[i];
}
for(int i=n-,j=k;i>=;i--) {
while(k>j && (t[k-]-t[k-]).det(p[i]-t[k-])<)
k--;
t[k++]=p[i];
}
if(n>) k--;
}
double areaPg()
{
double res=;
for(int i=;i<k-;i++)
res+=(t[i]-t[]).det(t[i+]-t[]);
return res/2.0;
}
void solve()
{
andrew();
int ans=areaPg()/;
printf("%d\n",ans);
} int main()
{
while(~scanf("%d",&n)) {
for(int i=;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
solve();
} return ;
}

最新文章

  1. 第10章 Shell编程(1)_正则表达式
  2. git rebase 和 reset的区别
  3. 让input框只能输入数字
  4. 追本溯源 解析“大数据生态环境”发展现状(CSDN)
  5. Creating HTML table with vertically oriented text as table header 表头文字方向
  6. CSS3:不可思议的border属性&amp;Web字体图标Font Awesome
  7. 构建linux内核源码树
  8. Android开源工具库
  9. php 半角与全角相关的正则
  10. 9、手把手教你Extjs5(九)使用MVVM特性控制菜单样式
  11. 获取FMS的状态信息
  12. git commit -m与-am的区别
  13. UiAutomator2.0升级填坑记
  14. laravel5.6中jquery+ajax分页
  15. autoperfixer 版本配置
  16. Kotlin基础学习
  17. while read line
  18. [Z]sql优化
  19. 初探 Yii2 的测试模式 index-test.php
  20. Leetcode 22

热门文章

  1. 简单介绍下怎么在spring中使用RabbitMQ
  2. Json数据交换一Gson
  3. thinkphp 模块部署
  4. poi之Excel(在线生成)下载
  5. JavaWeb学习篇之----Jsp详解
  6. dfs版容斥原理+剪枝——bzoj1853
  7. LeakCanary 与 鹅场Matrix ResourceCanary对比分析
  8. NX二次开发-NXOpen::WCS Class Reference
  9. 实现组件props双向绑定解决方案
  10. R语言中动态安装库