题目链接:http://lightoj.com/volume_showproblem.php?problem=1203

题意:给你一个点集,求凸包中最小的角;模板题,但是刚开始的时候模板带错了,错的我都想吐了;

#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define met(a, b) memset(a, b, sizeof(a))
const double eps = 1e-;
const double PI = acos(-);
const int N = ; struct point
{
double x, y;
point(double x=, double y=) : x(x), y(y){}
friend point operator - (const point& p1, const point& p2)
{
return point(p1.x-p2.x, p1.y-p2.y);
}
friend double operator ^ (const point& p1, const point& p2)
{
return p1.x*p2.y - p1.y*p2.x;
}
}p[N], res[N];
double Dist(point p1, point p2)
{
double dx = p1.x - p2.x, dy = p1.y - p2.y;
return sqrt(dx*dx + dy*dy);
}
bool cmp1(point p1, point p2)
{
if(p1.y == p2.y)
return p1.x < p2.x;
return p1.y < p2.y;
}
bool cmp2(point p1, point p2)///极角排序;若极角相同,距离近的在前面;
{
double k = (p1-p[])^(p2-p[]);
if( k>eps || (fabs(k)<eps && Dist(p1, p[]) < Dist(p2, p[]) ))
return ;
return ;
}
int Graham(int n)
{
res[] = p[];if(n == ) return ;
res[] = p[];if(n == ) return ;
int top = ;
for(int i=; i<n; i++)
{
while(top && ((res[top]-res[top-])^(p[i]-res[top-])) <= ) top--;
res[++top] = p[i];
}
return top+;
}
int main()
{
int n, T, tCase = ;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i=; i<n; i++)
scanf("%lf %lf", &p[i].x, &p[i].y);
sort(p, p+n, cmp1);///p[0]为最下方靠左的点;
sort(p+, p+n, cmp2);///以p[0]为基点,按叉积进行排序;
int cnt = Graham(n);///求凸包的顶点个数cnt,保存在res中,下标从0开始;
if(cnt < )
{
printf("Case %d: 0\n", tCase++);
continue;
}
double ans = ;
res[cnt] = res[], res[cnt+] = res[];
for(int i=; i<=cnt; i++)
{
double a = Dist(res[i-], res[i+]);
double b = Dist(res[i-], res[i]);
double c = Dist(res[i], res[i+]);
ans = min(ans, acos((b*b+c*c-a*a)/(*b*c)));
}
printf("Case %d: %.6f\n", tCase++, ans*/PI);
}
return ;
}

最新文章

  1. Masonry 创建Button的简单使用
  2. B. Factory Repairs--cf627B(线段树)
  3. Python3学习(2)-中级篇
  4. requirejs 笔记
  5. window 配置 sendmail
  6. 点击上下页,实现图片滚动的jquery代码
  7. Modelbuilder进阶教程
  8. 【2017-06-02】Jquery基础
  9. HDU 1014 Uniform Generator【GCD,水】
  10. Cocos2D中屏幕分辨率解释
  11. python 高级部分
  12. MicroSoft CryptoAPI data/file encrypt/decrypt
  13. 遇到的难题之一 —— js方法toFixd()
  14. SQL server 一些小结
  15. Linux查询端口是否被占用的四种方法
  16. Confluence 6 数据模型
  17. mysql主从复制延迟问题的相关知识与解决方案
  18. android控件RecyclerView中,如何显示自定义分割线以及最后一项去除分割线
  19. 移动端二三事【三】:transform的矩阵(matrix)操作、transform操作函数及注意事项
  20. 【Unity笔记】寻路导航用NavMeshObstacle做动态阻挡

热门文章

  1. Android环境搭建要点
  2. tableviewCell折叠状态2
  3. ArcEngine 异常 :The index passed was not within the valid range.
  4. sessions 表的架构过程
  5. excel表中内容如何反排列
  6. NP
  7. 【iCore、iCore2、iBoard例程】【异步FIFO跨时钟域通信(通过ARM 读FPGA FIFO)】
  8. 小红伞和virtualbox5.0.10冲突
  9. Mac OS 快捷键
  10. pycharm使用笔记