欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 1113 Wall(凸包)

程序员文章站 2022-03-29 21:23:23
...

题意:求城堡外面距离为L的城墙的周长,思路就是这个距离为L的城墙就是这个城堡的凸包的长度加上以L为半径的一个圆(扫了一周)。

 

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#define N 1001
const double PI = 3.141592654;
using namespace std;
struct node{
	double x, y;
	bool friend operator < (const node &a, const node &b){
		if(a.y == b.y)
			return a.x < b.x;
		return a.y < b.y;
	}
}point[N];

double calcurateDis(node a, node b){
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

bool judge(node a, node b, node c){
	return (a.x - c.x)*(b.y - c.y) >= (b.x - c.x)*(a.y - c.y);
}

double solve(int n){
	vector<node> tempPoint(n*2);
	sort(point, point + n);
	if(n == 0) return 0;
	if(n == 1){
		return 0;
	}
	if(n == 2){
		return calcurateDis(point[0], point[1]);
	}
	tempPoint[0] = point[0];
	tempPoint[1] = point[1];
	tempPoint[2] = point[2];
	int top = 1;
	for(int i = 2; i < n; i++){
		while(top != 0 && judge(point[i], tempPoint[top], tempPoint[top - 1]))	top--;
		tempPoint[++top] = point[i];
	}
	int len = top;
	tempPoint[++top] = point[n - 2];
	for(int i = n - 3; i >= 0; i--){
		while(top != len && judge(point[i], tempPoint[top], tempPoint[top - 1]))	top--;
		tempPoint[++top] = point[i];
	}
	double result = 0.0;
	for(int i = 1; i <= top; i++){
		result += calcurateDis(tempPoint[i], tempPoint[(i + 1) > top ? 1 : (i + 1)]);
	}
	return result;
}

int main(){
	int n, L;
	scanf("%d%d", &n, &L);
	for(int i = 0; i < n; i++)
		scanf("%lf%lf", &point[i].x, &point[i].y);
	printf("%.0f\n", solve(n) + 2 * PI * L);
	return 0;
}

 

相关标签: POJ 凸包