[kuangbin]计算几何之凸包问题

• Z时代
• 2024-01-10
• 分类：技术分享

POJ 1113 Wall

大意：

给出一个n边形的城堡，国王要求修建一个城墙，城墙到城堡的距离最少是L，问最少的城堡边长是多少，答案要求四舍五入到整数

思路：

很容易想到求凸包，但是要求到城堡的距离最少是L，所以仅仅求凸包是不够的，观察图像可以发现，最优的方法是凸包的每条边向外移动L，然后用圆形填充缝隙即可，也就是说，最终答案 是凸包边长+半径为L的圆的周长。

剩下就是纯模板了，注意答案要四舍五入，直接

printf("%d\n",(int)(res+0.5));

即可.

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <set>
using namespace std;
const int N = 20 + 5;
typedef long long LL;
int t, n;
double dis[100][100];
// 计算几何模板
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
// 和0做比较
int sgn(double x) {
if (fabs(x) < eps) return 0;  // =0
if (x < 0)
return -1;  // < 0
else
return 1;  // > 0
}
// 计算x的平方
inline double sqr(double x) { return x * x; }
struct Point {
double x, y;
int index;
Point() {}
Point(double _x, double _y) {
x = _x;
y = _y;
}
void input() { scanf("%lf%lf", &x, &y); }
void output() { printf("%.2f %.2f\n", x, y); }
bool operator==(Point b) const {
return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
}
bool operator<(Point b) const {
return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
}
Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
//叉积
double operator^(const Point &b) const { return x * b.y - y * b.x; }
//点积
double operator*(const Point &b) const { return x * b.x + y * b.y; }
//返回两点的距离
double dist(Point p) { return hypot(x - p.x, y - p.y); }
// 极角排序
};
struct Line {
Point s, e;
Line() {}
// 两点确定一条线段
Line(Point _s, Point _e) {
s = _s;
e = _e;
}
//返回点和直线(方向向量)关系
// 1  在左侧; 2  在右侧; 3  在直线上
int relation(Point p) {
int c = sgn((p - s) ^ (e - s));
if (c < 0)
return 1;
else if (c > 0)
return 2;
else
return 3;
}
//两线段相交判断:规范相交：交点不在端点
// 2 规范相交；1 非规范相交；0 不相交
int segcrossseg(Line v) {
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
int d3 = sgn((v.e - v.s) ^ (s - v.s));
int d4 = sgn((v.e - v.s) ^ (e - v.s));
if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 2;
return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
(d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
(d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
(d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
}
bool parallel(Line v) { return sgn((e - s) ^ (v.e - v.s)) == 0; }
//求两直线的交点
//要保证两直线不平行或重合
Point crosspoint(Line v) {
double a1 = (v.e - v.s) ^ (s - v.s);
double a2 = (v.e - v.s) ^ (e - v.s);
return Point((s.x * a2 - e.x * a1) / (a2 - a1),
(s.y * a2 - e.y * a1) / (a2 - a1));
}
double length() { return s.dist(e); }
//点到直线的距离
double dispointtoline(Point p) {
return fabs((p - s) ^ (e - s)) / length();
}
//点到线段的距离
double dispointtoseg(Point p) {
if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)
return min(p.dist(s), p.dist(e));
return dispointtoline(p);
}
//直线和线段相交判断
//-*this line   -v seg
// 2 规范相交
// 1 非规范相交
// 0 不相交
int linecrossseg(Line v) {
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
if ((d1 ^ d2) == -2) return 2;
return (d1 == 0 || d2 == 0);
}
};
struct polygon {
int n;
Point p[maxp];
Line l[maxp];
// 输入多边形
void input(int _n) {
n = _n;
for (int i = 0; i < n; i++) p[i].input();
}
// 加入一个点
void add(Point q) { p[n++] = q; }
// 得到多边形所有边的线段
void getline() {
for (int i = 0; i < n; i++) {
l[i] = Line(p[i], p[(i + 1) % n]);
}
}
// 极角排序
struct cmp {
Point p;
cmp(const Point &p0) { p = p0; }
bool operator()(const Point &aa, const Point &bb) {
Point a = aa, b = bb;
int d = sgn((a - p) ^ (b - p));
if (d == 0) {
return sgn(a.dist(p) - b.dist(p)) < 0;
}
return d > 0;
}
};
// 进行极角排序
// 首先需要找到最左下角的点
// 需要重载号好Point的 < 操作符(min函数要用)
void norm() {
Point mi = p[0];
for (int i = 1; i < n; i++)
mi = min(mi, p[i]);  // min函数用Point的<重载
sort(p, p + n, cmp(mi));
}
// 得到凸包
// 得到的凸包里面的点编号是0 ~ n-1的
// 两种凸包的方法
// 注意如果有影响，要特判下所有点共点，或者共线的特殊情况
void getconvex(polygon &convex) {
sort(p, p + n);
convex.n = n;
for (int i = 0; i < min(n, 2); i++) {
convex.p[i] = p[i];
}
if (convex.n == 2 && (convex.p[0] == convex.p[1])) convex.n--;  //特判
if (n <= 2) return;
int &top = convex.n;
top = 1;
for (int i = 2; i < n; i++) {
while (top && sgn((convex.p[top] - p[i]) ^
(convex.p[top - 1] - p[i])) <= 0)
top--;
convex.p[++top] = p[i];
}
int temp = top;
convex.p[++top] = p[n - 2];
for (int i = n - 3; i >= 0; i--) {
while (top != temp && sgn((convex.p[top] - p[i]) ^
(convex.p[top - 1] - p[i])) <= 0)
top--;
convex.p[++top] = p[i];
}
if (convex.n == 2 && (convex.p[0] == convex.p[1])) convex.n--;  //特判
convex.norm();  //`原来得到的是顺时针的点，排序后逆时针`
}
// 得到凸包的另外一种方法
void Graham(polygon &convex) {
norm();
int &top = convex.n;
top = 0;
if (n == 1) {
top = 1;
convex.p[0] = p[0];
return;
}
if (n == 2) {
top = 2;
convex.p[0] = p[0];
convex.p[1] = p[1];
if (convex.p[0] == convex.p[1]) top--;
return;
}
convex.p[0] = p[0];
convex.p[1] = p[1];
top = 2;
for (int i = 2; i < n; i++) {
while (top > 1 && sgn((convex.p[top - 1] - convex.p[top - 2]) ^
(p[i] - convex.p[top - 2])) <= 0)
top--;
convex.p[top++] = p[i];
}
if (convex.n == 2 && (convex.p[0] == convex.p[1])) convex.n--;  //特判
}
// 得到多边形的周长
double getcircumference() {
double sum = 0;
for (int i = 0; i < n; i++) {
sum += p[i].dist(p[(i + 1) % n]);
}
return sum;
}
};
double d;
polygon P;
int main(){
cin >> n >> d;
for (int i = 0; i < n;i++){
double x, y;
scanf("%lf%lf", &x, &y);
P.add(Point(x, y));
}
polygon wal;
P.Graham(wal);
printf("%d\n",(int)(wal.getcircumference()+2*pi*d+0.5));
}

POJ 2007 Scrambled Polygon

大意：

讲了一堆概念...极角排序即可

思路：

模板题

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <set>
using namespace std;
const int N = 20 + 5;
typedef long long LL;
int t, n;
double dis[100][100];
// 计算几何模板
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
// 和0做比较
int sgn(double x) {
if (fabs(x) < eps) return 0;  // =0
if (x < 0)
return -1;  // < 0
else
return 1;  // > 0
}
// 计算x的平方
inline double sqr(double x) { return x * x; }
struct Point {
double x, y;
int index;
Point() {}
Point(double _x, double _y) {
x = _x;
y = _y;
}
void input() { scanf("%lf%lf", &x, &y); }
void output() { printf("%.2f %.2f\n", x, y); }
bool operator==(Point b) const {
return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
}
bool operator<(Point b) const {
return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
}
Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
//叉积
double operator^(const Point &b) const { return x * b.y - y * b.x; }
//点积
double operator*(const Point &b) const { return x * b.x + y * b.y; }
//返回两点的距离
double dist(Point p) { return hypot(x - p.x, y - p.y); }
// 极角排序
};
struct Line {
Point s, e;
Line() {}
// 两点确定一条线段
Line(Point _s, Point _e) {
s = _s;
e = _e;
}
//返回点和直线(方向向量)关系
// 1  在左侧; 2  在右侧; 3  在直线上
int relation(Point p) {
int c = sgn((p - s) ^ (e - s));
if (c < 0)
return 1;
else if (c > 0)
return 2;
else
return 3;
}
//两线段相交判断:规范相交：交点不在端点
// 2 规范相交；1 非规范相交；0 不相交
int segcrossseg(Line v) {
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
int d3 = sgn((v.e - v.s) ^ (s - v.s));
int d4 = sgn((v.e - v.s) ^ (e - v.s));
if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 2;
return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
(d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
(d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
(d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
}
bool parallel(Line v) { return sgn((e - s) ^ (v.e - v.s)) == 0; }
//求两直线的交点
//要保证两直线不平行或重合
Point crosspoint(Line v) {
double a1 = (v.e - v.s) ^ (s - v.s);
double a2 = (v.e - v.s) ^ (e - v.s);
return Point((s.x * a2 - e.x * a1) / (a2 - a1),
(s.y * a2 - e.y * a1) / (a2 - a1));
}
double length() { return s.dist(e); }
//点到直线的距离
double dispointtoline(Point p) {
return fabs((p - s) ^ (e - s)) / length();
}
//点到线段的距离
double dispointtoseg(Point p) {
if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)
return min(p.dist(s), p.dist(e));
return dispointtoline(p);
}
//直线和线段相交判断
//-*this line   -v seg
// 2 规范相交
// 1 非规范相交
// 0 不相交
int linecrossseg(Line v) {
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
if ((d1 ^ d2) == -2) return 2;
return (d1 == 0 || d2 == 0);
}
};
struct polygon {
int n;
Point p[maxp];
Line l[maxp];
// 输入多边形
void input(int _n) {
n = _n;
for (int i = 0; i < n; i++) p[i].input();
}
// 加入一个点
void add(Point q) { p[n++] = q; }
// 得到多边形所有边的线段
void getline() {
for (int i = 0; i < n; i++) {
l[i] = Line(p[i], p[(i + 1) % n]);
}
}
// 极角排序
struct cmp {
Point p;
cmp(const Point &p0) { p = p0; }
bool operator()(const Point &aa, const Point &bb) {
Point a = aa, b = bb;
int d = sgn((a - p) ^ (b - p));
if (d == 0) {
return sgn(a.dist(p) - b.dist(p)) < 0;
}
return d > 0;
}
};
// 进行极角排序
// 首先需要找到最左下角的点
// 需要重载号好Point的 < 操作符(min函数要用)
void norm() {
Point mi = Point(0, 0);
sort(p, p + n, cmp(mi));
}
};
double d;
polygon P;
int main(){
double x, y;
while(scanf("%lf%lf", &x, &y)!=EOF){
P.add(Point(x, y));
}
P.norm();
for (int i = 0; i < P.n;i++){
printf("(%.0f,%.0f)\n", P.p[i].x, P.p[i].y);
}
}

POJ 1873 The Fortified Forest

大意：

给出n\((n<=15)\)颗树，每颗树都有自己的价值和木材值，现在需要砍掉一些树用他们的木材值做围栏围住其他的树，问能保留最大价值的方案是什么,如果价值相同，则选择砍树颗数最少的

思路：

因为n很小，所以可以想到二进制枚举，然后计算没被砍的树的凸包即可

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int N = 20 + 5;
typedef long long LL;
double dis[100][100];
// 计算几何模板
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 20;
// 和0做比较
int sgn(double x) {
if (fabs(x) < eps) return 0;  // =0
if (x < 0)
return -1;  // < 0
else
return 1;  // > 0
}
// 计算x的平方
inline double sqr(double x) { return x * x; }
struct Point {
double x, y;
int index;
Point() {}
Point(double _x, double _y) {
x = _x;
y = _y;
}
void input() { scanf("%lf%lf", &x, &y); }
void output() { printf("%.2f %.2f\n", x, y); }
bool operator==(Point b) const {
return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
}
bool operator<(Point b) const {
return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
}
Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
//叉积
double operator^(const Point &b) const { return x * b.y - y * b.x; }
//点积
double operator*(const Point &b) const { return x * b.x + y * b.y; }
//返回两点的距离
double dist(Point p) {
return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}
// 极角排序
};
struct polygon {
int n;
Point p[maxp];
// 输入多边形
void input(int _n) {
n = _n;
for (int i = 0; i < n; i++) p[i].input();
}
// 加入一个点
void add(Point q) { p[n++] = q; }
// 得到多边形所有边的线段
// 极角排序
struct cmp {
Point p;
cmp(const Point &p0) { p = p0; }
bool operator()(const Point &aa, const Point &bb) {
Point a = aa, b = bb;
int d = sgn((a - p) ^ (b - p));
if (d == 0) {
return sgn(a.dist(p) - b.dist(p)) < 0;
}
return d > 0;
}
};
// 进行极角排序
// 首先需要找到最左下角的点
// 需要重载号好Point的 < 操作符(min函数要用)
void norm() {
Point mi = p[0];
for (int i = 1; i < n; i++) mi = min(mi, p[i]);  // min函数用Point的<重载
sort(p, p + n, cmp(mi));
}
void Graham(polygon &convex) {
norm();
int &top = convex.n;
top = 0;
if (n == 1) {
top = 1;
convex.p[0] = p[0];
return;
}
if (n == 2) {
top = 2;
convex.p[0] = p[0];
convex.p[1] = p[1];
if (convex.p[0] == convex.p[1]) top--;
return;
}
convex.p[0] = p[0];
convex.p[1] = p[1];
top = 2;
for (int i = 2; i < n; i++) {
while (top > 1 && sgn((convex.p[top - 1] - convex.p[top - 2]) ^
(p[i] - convex.p[top - 2])) <= 0)
top--;
convex.p[top++] = p[i];
}
if (convex.n == 2 && (convex.p[0] == convex.p[1])) convex.n--;  //特判
}
// 得到多边形的周长
double getcircumference() {
double sum = 0;
for (int i = 0; i < n; i++) {
sum += p[i].dist(p[(i + 1) % n]);
}
return sum;
}
};
double v[20], l[20];
polygon P,temp,t;
int main() {
double x, y;
int k = 0, n;
while (scanf("%d", &n) != EOF && n != 0) {
k++;
P.n = 0;
for (int i = 0; i < n; i++) {
scanf("%lf%lf%lf%lf", &x, &y, &v[i], &l[i]);
P.add(Point(x, y));
}
int MN = 1 << n;
double maxvul = 0.0, extra = 0;
int res[20], cnt = 0;
for (int i = 0; i < MN; i++) {
temp.n = 0;
double wood = 0, vul = 0;
int tempcnt = 0;
int havecnt = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
temp.add(P.p[j]);
vul += v[j];
} else {
wood += l[j];
tempcnt++;
}
}
t.n = 0;
temp.Graham(t);
double need = t.getcircumference();
if (wood >= need) {
if (maxvul < vul || (maxvul == vul && cnt > tempcnt)) {
maxvul = vul;
cnt = 0;
for (int j = 0; j < n; j++) {
if (!(i & (1 << j))) {
res[cnt++] = j;
}
}
extra = wood - need;
}
}
}
if (k != 1) {
printf("\n");
}
printf("Forest %d\n", k);
printf("Cut these trees:");
for (int i = 0; i < cnt; i++) {
printf(" %d", res[i] + 1);
}
printf("\nExtra wood: %.2lf\n", extra);
}
}

POJ 1228 Grandpa's Estate

大意：

原本有一个凸包，现在其中的一部分点已经丢失了，现在给你剩余的点，问根据这些点能否确定原本的凸包形状

思路：

判断是否是稳定凸包即可，即凸包上每个边都有至少三个点。记得特判所有的点共线的情况。

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int N = 20 + 5;
typedef long long LL;
double dis[100][100];
// 计算几何模板
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
// 和0做比较
int sgn(double x) {
if (fabs(x) < eps) return 0;  // =0
if (x < 0)
return -1;  // < 0
else
return 1;  // > 0
}
// 计算x的平方
inline double sqr(double x) { return x * x; }
struct Point {
double x, y;
int index;
Point() {}
Point(double _x, double _y) {
x = _x;
y = _y;
}
void input() { scanf("%lf%lf", &x, &y); }
void output() { printf("%.2f %.2f\n", x, y); }
bool operator==(Point b) const {
return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
}
bool operator<(Point b) const {
return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
}
Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
//叉积
double operator^(const Point &b) const { return x * b.y - y * b.x; }
//点积
double operator*(const Point &b) const { return x * b.x + y * b.y; }
//返回两点的距离
double dist(Point p) {
return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}
// 极角排序
};
struct Line {
Point s, e;
Line() {}
// 两点确定一条线段
Line(Point _s, Point _e) {
s = _s;
e = _e;
}
//返回点和直线(方向向量)关系
// 1  在左侧; 2  在右侧; 3  在直线上
int relation(Point p) {
int c = sgn((p - s) ^ (e - s));
if (c < 0)
return 1;
else if (c > 0)
return 2;
else
return 3;
}
//两线段相交判断:规范相交：交点不在端点
// 2 规范相交；1 非规范相交；0 不相交
int segcrossseg(Line v) {
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
int d3 = sgn((v.e - v.s) ^ (s - v.s));
int d4 = sgn((v.e - v.s) ^ (e - v.s));
if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 2;
return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
(d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
(d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
(d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
}
bool parallel(Line v) { return sgn((e - s) ^ (v.e - v.s)) == 0; }
//求两直线的交点
//要保证两直线不平行或重合
Point crosspoint(Line v) {
double a1 = (v.e - v.s) ^ (s - v.s);
double a2 = (v.e - v.s) ^ (e - v.s);
return Point((s.x * a2 - e.x * a1) / (a2 - a1),
(s.y * a2 - e.y * a1) / (a2 - a1));
}
double length() { return s.dist(e); }
//点到直线的距离
double dispointtoline(Point p) {
return fabs((p - s) ^ (e - s)) / length();
}
//点到线段的距离
double dispointtoseg(Point p) {
if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)
return min(p.dist(s), p.dist(e));
return dispointtoline(p);
}
//直线和线段相交判断
//-*this line   -v seg
// 2 规范相交
// 1 非规范相交
// 0 不相交
int linecrossseg(Line v) {
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
if ((d1 ^ d2) == -2) return 2;
return (d1 == 0 || d2 == 0);
}
};
struct polygon {
int n;
Point p[maxp];
// 输入多边形
void input(int _n) {
n = _n;
for (int i = 0; i < n; i++) p[i].input();
}
// 加入一个点
void add(Point q) { p[n++] = q; }
// 得到多边形所有边的线段
// 极角排序
struct cmp {
Point p;
cmp(const Point &p0) { p = p0; }
bool operator()(const Point &aa, const Point &bb) {
Point a = aa, b = bb;
int d = sgn((a - p) ^ (b - p));
if (d == 0) {
return sgn(a.dist(p) - b.dist(p)) < 0;
}
return d > 0;
}
};
// 进行极角排序
// 首先需要找到最左下角的点
// 需要重载号好Point的 < 操作符(min函数要用)
void norm() {
Point mi = p[0];
for (int i = 1; i < n; i++)
mi = min(mi, p[i]);  // min函数用Point的<重载
sort(p, p + n, cmp(mi));
}
void Graham(polygon &convex) {
norm();
int &top = convex.n;
top = 0;
if (n == 1) {
top = 1;
convex.p[0] = p[0];
return;
}
if (n == 2) {
top = 2;
convex.p[0] = p[0];
convex.p[1] = p[1];
if (convex.p[0] == convex.p[1]) top--;
return;
}
convex.p[0] = p[0];
convex.p[1] = p[1];
top = 2;
for (int i = 2; i < n; i++) {
while (top > 1 && sgn((convex.p[top - 1] - convex.p[top - 2]) ^
(p[i] - convex.p[top - 2])) <= 0)
top--;
convex.p[top++] = p[i];
}
if (convex.n == 2 && (convex.p[0] == convex.p[1])) convex.n--;  //特判
}
// 得到多边形的周长
double getcircumference() {
double sum = 0;
for (int i = 0; i < n; i++) {
sum += p[i].dist(p[(i + 1) % n]);
}
return sum;
}
};
int t, n;
double v[20], l[20];
polygon P, tb;
int main() {
scanf("%d", &t);
while (t--) {
P.n = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
double x, y;
scanf("%lf%lf", &x, &y);
P.add(Point(x, y));
}
tb.n = 0;
P.Graham(tb);
if (tb.n <= 2) {
cout << "NO" << endl;
continue;
}
int flag = 1;
for (int i = 0; i < tb.n; i++) {
Line now = Line(tb.p[i], tb.p[(i + 1) % tb.n]);
int num = 0;
for (int j = 0; j < P.n; j++) {
if (now.relation(P.p[j]) == 3) {
num++;
}
}
if (num < 3) {
flag = 0;
}
}
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}

POJ 3348 Cows

大意：

每个奶牛至少需要50平方米的土地，给出n个树，问从这些树里面选出牧场的端点，最多能养多少奶牛

思路：

凸包求面积，除以50即可，模板题,求面积利用原点到顶点组成的三角形叉积和即可。

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int N = 20 + 5;
typedef long long LL;
double dis[100][100];
// 计算几何模板
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 10000 + 5;
// 和0做比较
int sgn(double x) {
if (fabs(x) < eps) return 0;  // =0
if (x < 0)
return -1;  // < 0
else
return 1;  // > 0
}
// 计算x的平方
inline double sqr(double x) { return x * x; }
struct Point {
double x, y;
int index;
Point() {}
Point(double _x, double _y) {
x = _x;
y = _y;
}
void input() { scanf("%lf%lf", &x, &y); }
void output() { printf("%.2f %.2f\n", x, y); }
bool operator==(Point b) const {
return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
}
bool operator<(Point b) const {
return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
}
Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
//叉积
double operator^(const Point &b) const { return x * b.y - y * b.x; }
//点积
double operator*(const Point &b) const { return x * b.x + y * b.y; }
//返回两点的距离
double dist(Point p) {
return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}
// 极角排序
};
struct Line {
Point s, e;
Line() {}
// 两点确定一条线段
Line(Point _s, Point _e) {
s = _s;
e = _e;
}
//返回点和直线(方向向量)关系
// 1  在左侧; 2  在右侧; 3  在直线上
int relation(Point p) {
int c = sgn((p - s) ^ (e - s));
if (c < 0)
return 1;
else if (c > 0)
return 2;
else
return 3;
}
//两线段相交判断:规范相交：交点不在端点
// 2 规范相交；1 非规范相交；0 不相交
int segcrossseg(Line v) {
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
int d3 = sgn((v.e - v.s) ^ (s - v.s));
int d4 = sgn((v.e - v.s) ^ (e - v.s));
if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 2;
return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
(d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
(d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
(d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
}
bool parallel(Line v) { return sgn((e - s) ^ (v.e - v.s)) == 0; }
//求两直线的交点
//要保证两直线不平行或重合
Point crosspoint(Line v) {
double a1 = (v.e - v.s) ^ (s - v.s);
double a2 = (v.e - v.s) ^ (e - v.s);
return Point((s.x * a2 - e.x * a1) / (a2 - a1),
(s.y * a2 - e.y * a1) / (a2 - a1));
}
double length() { return s.dist(e); }
//点到直线的距离
double dispointtoline(Point p) {
return fabs((p - s) ^ (e - s)) / length();
}
//点到线段的距离
double dispointtoseg(Point p) {
if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)
return min(p.dist(s), p.dist(e));
return dispointtoline(p);
}
//直线和线段相交判断
//-*this line   -v seg
// 2 规范相交
// 1 非规范相交
// 0 不相交
int linecrossseg(Line v) {
int d1 = sgn((e - s) ^ (v.s - s));
int d2 = sgn((e - s) ^ (v.e - s));
if ((d1 ^ d2) == -2) return 2;
return (d1 == 0 || d2 == 0);
}
};
struct polygon {
int n;
Point p[maxp];
// 输入多边形
void input(int _n) {
n = _n;
for (int i = 0; i < n; i++) p[i].input();
}
// 加入一个点
void add(Point q) { p[n++] = q; }
// 得到多边形所有边的线段
// 极角排序
struct cmp {
Point p;
cmp(const Point &p0) { p = p0; }
bool operator()(const Point &aa, const Point &bb) {
Point a = aa, b = bb;
int d = sgn((a - p) ^ (b - p));
if (d == 0) {
return sgn(a.dist(p) - b.dist(p)) < 0;
}
return d > 0;
}
};
// 进行极角排序
// 首先需要找到最左下角的点
// 需要重载号好Point的 < 操作符(min函数要用)
void norm() {
Point mi = p[0];
for (int i = 1; i < n; i++)
mi = min(mi, p[i]);  // min函数用Point的<重载
sort(p, p + n, cmp(mi));
}
void Graham(polygon &convex) {
norm();
int &top = convex.n;
top = 0;
if (n == 1) {
top = 1;
convex.p[0] = p[0];
return;
}
if (n == 2) {
top = 2;
convex.p[0] = p[0];
convex.p[1] = p[1];
if (convex.p[0] == convex.p[1]) top--;
return;
}
convex.p[0] = p[0];
convex.p[1] = p[1];
top = 2;
for (int i = 2; i < n; i++) {
while (top > 1 && sgn((convex.p[top - 1] - convex.p[top - 2]) ^
(p[i] - convex.p[top - 2])) <= 0)
top--;
convex.p[top++] = p[i];
}
if (convex.n == 2 && (convex.p[0] == convex.p[1])) convex.n--;  //特判
}
// 得到多边形的周长
double getcircumference() {
double sum = 0;
for (int i = 0; i < n; i++) {
sum += p[i].dist(p[(i + 1) % n]);
}
return sum;
}
double getarea() {
double sum = 0;
for (int i = 0; i < n; i++) {
sum += (p[i] ^ p[(i + 1) % n]);
}
return fabs(sum) / 2;
}
};
int t, n;
double v[20], l[20];
polygon P, tb;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
double x, y;
scanf("%lf%lf", &x, &y);
P.add(Point(x, y));
}
P.Graham(tb);
double area=tb.getarea();
printf("%d\n", int(area / 50));
}

以上是 [kuangbin]计算几何之凸包问题 的全部内容， 来源链接： utcz.com/a/77533.html