博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 3348 Cows | 凸包——童年的回忆(误)
阅读量:5140 次
发布时间:2019-06-13

本文共 1726 字,大约阅读时间需要 5 分钟。

想当年……还是邱神给我讲的凸包来着……

#include 
#include
#include
#include
#define eps 0.000000001#define enter putchar('\n')#define space putchar(' ')using namespace std;typedef long long ll;template
void read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x;}template
void write(T x){ if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10);}const int N = 10005, INF = 0x3f3f3f3f;int n, top, ans;struct point { int x, y; point(){} point(int _x, int _y): x(_x), y(_y){} point operator - (point b) const{ return point(x - b.x, y - b.y); } int operator * (point b){ return x * b.y - y * b.x; } int norm(){ return x * x + y * y; }} p[N], stk[N], root;bool operator < (const point &a, const point &b){ int det = (a - root) * (b - root); if(det) return det > 0; return (a - root).norm() < (b - root).norm();}void graham(){ int pos = 0; root.x = root.y = INF; for(int i = 1; i <= n; i++) if(p[i].x < root.x || (p[i].x == root.x && p[i].y < root.y)) root = p[i], pos = i; if(pos != 1) swap(p[pos], p[1]); sort(p + 2, p + n + 1); stk[top = 1] = root; for(int i = 2; i <= n; i++){ while(top >= 2 && (stk[top] - stk[top - 1]) * (p[i] - stk[top - 1]) < 0) top--; stk[++top] = p[i]; }}void getarea(){ stk[top + 1] = stk[1]; for(int i = 1; i <= top; i++) ans += stk[i] * stk[i + 1];}int main(){ read(n); for(int i = 1; i <= n; i++) read(p[i].x), read(p[i].y); graham(); getarea(); write(ans / 2 / 50), enter; return 0;}

转载于:https://www.cnblogs.com/RabbitHu/p/POJ3348.html

你可能感兴趣的文章
jQuery on(),live(),trigger()
查看>>
【架构】Linux的架构(architecture)
查看>>
ASM 图解
查看>>
Date Picker控件:
查看>>
你的第一个Django程序
查看>>
treegrid.bootstrap使用说明
查看>>
[Docker]Docker拉取,上传镜像到Harbor仓库
查看>>
javascript 浏览器类型检测
查看>>
nginx 不带www到www域名的重定向
查看>>
记录:Android中StackOverflow的问题
查看>>
导航,头部,CSS基础
查看>>
[草稿]挂载新硬盘
查看>>
[USACO 2017 Feb Gold] Tutorial
查看>>
关于mysql中GROUP_CONCAT函数的使用
查看>>
OD使用教程20 - 调试篇20
查看>>
Java虚拟机(JVM)默认字符集详解
查看>>
Java Servlet 过滤器与 springmvc 拦截器的区别?
查看>>
(tmp >> 8) & 0xff;
查看>>
linux命令之ifconfig详细解释
查看>>
NAT地址转换
查看>>