【背景】话说Mr.一首歌根本不会计算几何此等神物啊，但是当小学妹问起自己凸包神马的东西时，自己幸好还收藏着一个模版，于是就给了人家模版看，叫人家看懂ｇｒａｈａｍ思想后再来交流，这才发现要开始好好学计算几何了（此等动机不纯，小朋友们千万不要学我这个坏榜样）。
１.基础
❤多边形重心的计算
求多边形重心的题目大致有这么几种：
1、质量集中在顶点上
n个顶点坐标为(xi,yi)，质量为mi，则重心
X = ∑( xi×mi ) / ∑mi
Y = ∑( yi×mi ) / ∑mi
特殊地，若每个点的质量相同，则
X = ∑xi / n
Y = ∑yi / n
2、质量分布均匀
特殊地，质量均匀的三角形重心：
X = ( x0 + x1 + x2 ) / 3
Y = ( y0 + y1 + y2 ) / 3
3、质量分布不均匀
只能用函数多重积分来算，不太会
这题的做法：
将n边形分成多个三角形，分别求出重心坐标以及质量m【因为质量分布均匀，所以可以设密度为1，则面积就是质量】
因为质量都集中在重心
所以把所有求出来的重心按逆时针连接起来又是一个多边形
但是这个多边形的质量集中在顶点上
所以可以利用上面公式进行计算
例：
hdu1115
hdu1115
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1000100;
struct point 
{ double x,y; }pnt[maxn] , g;
double det(point sp,point ep,point op){
return (sp.x-op.x)*(ep.y-op.y) - (ep.x-op.x)*(sp.y-op.y);
}
void compGravity(point pnt[] , int n) {
point tmp;
double sumArea , area;
sumArea = 0;
g.x = g.y = 0;
for(int i=2;i<n;i++) {
area = det(pnt[i-1],pnt[i],pnt[0]);
sumArea += area;
tmp.x = pnt[0].x + pnt[i-1].x + pnt[i].x;
tmp.y = pnt[0].y + pnt[i-1].y + pnt[i].y;
g.x += tmp.x * area;
g.y += tmp.y * area;
}
g.x /= (sumArea * 3.0);
g.y /= (sumArea * 3.0);
}
int main() {
int T , n;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
compGravity(pnt , n);
printf("%.2lf %.2lf\n",g.x,g.y);
}
return 0;
}
❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤
２.凸包
㈠graham扫描法的一些应用
graham模版
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct point { double x,y; };
bool mult(point sp,point ep,point op){
return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y);
}
bool operator < (const point &l,const point &r){
return l.y<r.y || (l.y==r.y && l.x < r.x);
}
int graham(point pnt[],int n,point res[]){ //pnt是图中的所有的点，res是通过判断后在凸边行边上的点，而且这些点都是按逆时针存储的，n是所有点的个数
int i,len,k = 0,top = 1;
sort(pnt,pnt+n);
if(n == 0) return 0; res[0]=pnt[0];
if(n == 1) return 1; res[1]=pnt[1];
if(n == 2) return 2; res[2]=pnt[2];
for(i=2;i<n;i++) {
while(top && mult(pnt[i],res[top],res[top-1]))
top--;
res[++top] = pnt[i];
}
len = top; res[++top] = pnt[n-2];
for(i=n-3;i>=0;i--){
while(top!=len && mult(pnt[i],res[top],res[top-1]))
top--;
res[++top]=pnt[i];
}
return top; // 返回凸包中点的个数
}
①
hdu1392 求凸包周长
求得凸包后，求出相邻点的距离总和即可
point res[100001],pnt[100001];
double stlen(point a,point b){
return sqrt(pow((b.x-a.x),2) + pow((b.y-a.y),2));
}
int main(){
int n,i,k;
double len;
while(cin>>n && n){
len = 0.0;
for(i=0;i<n;i++)
cin>>pnt[i].x>>pnt[i].y;
if(n==1) { cout<<"0.00"<<endl;continue; }
if(n==2) { printf("%.2lf\n",stlen(pnt[0],pnt[1]));continue; }
k = graham(pnt,n,res);
for(i=1;i<=k;i++)
len += stlen(res[i-1],res[i]);
printf("%.2lf\n",len);
}
return 0;
}
②
hdu2202 求最大三角形：找到了凸包的点，同过叉积求三角形的面，最终找出最大的就OK了
point res[50001],pnt[50001];
double area(point a,point b,point c){ //利用叉积来算面积
return abs((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x));
}
int main(){
int t,n,i,j,s;
double ar,Max;
while(cin>>n){
ar = 0.0;
Max = 0.0;
for(i=0;i<n;i++)
cin>>pnt[i].x>>pnt[i].y;
int k = graham(pnt,n,res);
for(j=0;j<k-2;j++){
for(i=j+1;i<k-1;i++)
for(s=i+1;s<k;s++){
ar=area(res[i],res[j],res[s]);
if(Max<ar) Max = ar;
}
}
printf("%.2lf\n",Max/2);
}
return 0;
}
③
hdu3285 题目要把凸包边上的点输出，输出有两个规则，
1.按照y的值最大的先输出，如果一值相等就按照X值小的先输出。
2.之后要按照顺时针输出点的位置。当时自己在做的时候，用的凸包模板，凸包上的点是按逆时针保存，而却没有1条那样的规则，后来到，把逆时针倒过来就是顺时针，在去找到那个满足第一个条件的那个点在数组中位置，再从找到的位置输出就行了
point res[100001],pnt[100001],re[100001];
double stlen(point a,point b){
return sqrt(pow((b.x-a.x),2)+pow((b.y-a.y),2));
}
int main(){
int n,i,j,k,m,d,f;
cin>>n;
while(n--){
cin>>k>>m;
int may = -(1<<29),mix=(1<<29);
for(i=0;i<m;i++)
cin>>pnt[i].x>>pnt[i].y;
d = graham(pnt,m,res);
cout<<k<<" "<<d<<endl;
for(i=d-1,j=0;i>=0;i--)
re[j++] = res[i];
for(i=0;i<d;i++){
if(re[i].y>may){
may=re[f=i].y;
mix=re[i].x;
}
if(re[i].y==may && re[i].x<mix)
mix=re[f=i].x;
}
for(i=f;i<d;i++)
cout<<re[i].x<<" "<<re[i].y<<endl;
for(i=0;i<f;i++)
cout<<re[i].x<<" "<<re[i].y<<endl;
}
return 0;
}
④
poj1113 求出凸包的周长再加上一L为半径的圆的周长就是要求的
#define pi acos(-1.0)
double Dis(point p1,point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
point p[1000],res[1000];
int main(){
int n,len,i,s;
double dis;
while(~scanf("%d%d",&n,&len)){
for(i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
s = graham(p,n,res);
dis = 0;
for(i=0;i<s-1;i++)
dis += Dis(res[i],res[i+1]);
dis += Dis(res[s-1],res[0]);
dis += 2 * pi * len;
printf("%.f\n",dis);
}
return 0;
}今天就到这里了，谢谢各位关心：） 22:53 2012/9/8 by Mr.一首歌
posted on 2012-09-08 22:20
Mr.OneSong 阅读(382)
评论(0) 编辑 收藏 引用