首页 > 代码库 > LightOJ 1239 - Convex Fence 凸包周长
LightOJ 1239 - Convex Fence 凸包周长
LINK
题意:类似POJ的宫殿围墙那道,只不过这道题数据稍微强了一点,有共线的情况
思路:求凸包周长加一个圆周长
/** @Date : 2017-07-20 15:46:44 * @FileName: LightOJ 1239 求凸包.cpp * @Platform: Windows * @Author : Lweleth (SoungEarlf@gmail.com) * @Link : https://github.com/ * @Version : $Id$ */#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#include <utility>#include <vector>#include <map>#include <set>#include <string>#include <stack>#include <queue>#include <math.h>//#include <bits/stdc++.h>#define LL long long#define PII pair<int ,int>#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;const double Pi = acos(-1.0);struct point{ double x, y; point(){} point(double _x, double _y){x = _x, y = _y;} point operator -(const point &b) const { return point(x - b.x, y - b.y); } double operator *(const point &b) const { return x * b.x + y * b.y; } double operator ^(const point &b) const { return x * b.y - y * b.x; }};double xmult(point p1, point p2, point p0) { return (p1 - p0) ^ (p2 - p0); } double distc(point a, point b){ return sqrt((double)((b - a) * (b - a)));}int sign(double x){ if(fabs(x) < eps) return 0; if(x < 0) return -1; else return 1;}////////int n;point stk[N];point p[N];int cmpC(point a, point b)//水平序排序{ return sign(a.x - b.x) < 0 || (sign(a.x - b.x) == 0 && sign(a.y - b.y) < 0);}int Graham(point *p, int n)//水平序{ sort(p, p + n, cmpC); int top = 0; for(int i = 0; i < n; i++) { while(top >= 2 && sign(xmult(stk[top - 2], stk[top - 1], p[i])) < 0) top--; stk[top++] = p[i]; } int tmp = top; for(int i = n - 2; i >= 0; i--) { while(top > tmp && sign(xmult(stk[top - 2],stk[top - 1] ,p[i] )) < 0) top--; stk[top++] = p[i]; } if(n > 1) top--; return top;}int main(){ int T; cin >> T; int c = 0; while(T--) { int n; double l; cin >> n >> l; double x, y; for(int i = 0; i < n; i++) { scanf("%lf%lf", &x, &y); p[i] = point(x, y); } int m = Graham(p, n); double ans = 2 * Pi * l; stk[m++] = stk[0];//注意只有直线的情况 for(int i = 0; i < m - 1; i++) ans += distc(stk[i], stk[i + 1]); printf("Case %d: %.10lf\n", ++c, ans); } return 0;}
LightOJ 1239 - Convex Fence 凸包周长
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。