【背景】话说Mr.一首歌根本不会计算几何此等神物啊,但是当小学妹问起自己凸包神马的东西时,自己幸好还收藏着一个模版,于是就给了人家模版看,叫人家看懂graham思想后再来交流,这才发现要开始好好学计算几何了(此等动机不纯,小朋友们千万不要学我这个坏榜样)。
1.基础
❤多边形重心的计算
求多边形重心的题目大致有这么几种:
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
![](/Images/OutliningIndicators/ContractedBlock.gif)
hdu1115
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1000100;
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct point
{ double x,y; }pnt[maxn] , g;
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
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);
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
void compGravity(point pnt[] , int n)
{
point tmp;
double sumArea , area;
sumArea = 0;
g.x = g.y = 0;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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);
}
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int T , n;
scanf("%d",&T);
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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;
}
![](/Images/OutliningIndicators/None.gif)
❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤
2.凸包
㈠graham扫描法的一些应用
![](/Images/OutliningIndicators/ContractedBlock.gif)
graham模版
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct point
{ double x,y; };
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
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);
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool operator < (const point &l,const point &r)
{
return l.y<r.y || (l.y==r.y && l.x < r.x);
}
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
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];
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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];
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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; // 返回凸包中点的个数
}
![](/Images/OutliningIndicators/None.gif)
①
hdu1392 求凸包周长
求得凸包后,求出相邻点的距离总和即可
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
point res[100001],pnt[100001];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
double stlen(point a,point b)
{
return sqrt(pow((b.x-a.x),2) + pow((b.y-a.y),2));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int n,i,k;
double len;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(cin>>n && n)
{
len = 0.0;
for(i=0;i<n;i++)
cin>>pnt[i].x>>pnt[i].y;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(n==1)
{ cout<<"0.00"<<endl;continue; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
②
hdu2202 求最大三角形:找到了凸包的点,同过叉积求三角形的面,最终找出最大的就OK了
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
point res[50001],pnt[50001];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
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));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int t,n,i,j,s;
double ar,Max;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j=0;j<k-2;j++)
{
for(i=j+1;i<k-1;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
③
hdu3285 题目要把凸包边上的点输出,输出有两个规则,
1.按照y的值最大的先输出,如果一值相等就按照X值小的先输出。
2.之后要按照顺时针输出点的位置。当时自己在做的时候,用的凸包模板,凸包上的点是按逆时针保存,而却没有1条那样的规则,后来到,把逆时针倒过来就是顺时针,在去找到那个满足第一个条件的那个点在数组中位置,再从找到的位置输出就行了
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
point res[100001],pnt[100001],re[100001];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
double stlen(point a,point b)
{
return sqrt(pow((b.x-a.x),2)+pow((b.y-a.y),2));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int n,i,j,k,m,d,f;
cin>>n;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0;i<d;i++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
④
poj1113 求出凸包的周长再加上一L为半径的圆的周长就是要求的
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
#define pi acos(-1.0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
double Dis(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
point p[1000],res[1000];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int n,len,i,s;
double dis;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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 阅读(351)
评论(0) 编辑 收藏 引用