题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3685题目大意：给出一个物体，假设密度均匀，z轴所有高都相同，在xy平面的投影是多边形，即由平面拉伸成立体，求使物体能平稳放置的方法有多少种？
题解：计算几何，解法不难想到。
1.计算多边形的重心(三角形剖分法)
2.计算凸包(想象一下物体放的时候)
3.枚举凸包上每一条边，看看重心的投影是否落在边上(不含边端点)
代码：
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
using namespace std;
const double eps = 1.0e-8;
int doubleCmp(const double _value)
{
if(fabs(_value) < eps)
{
return 0;
}
else
{
return (_value > 0)?1:-1;
}
}
class Point
{
public:
double x;
double y;
public:
Point(const double _x = 0,const double _y = 0)
:x(_x),y(_y)
{
}
Point(const Point& _point)
{
this->x = _point.x;
this->y = _point.y;
}
double GetX()const{return x;}
double GetY()const{return y;}
void SetX(const double _x){x = _x;}
void SetY(const double _y){y = _y;}
void Set(const double _x,const double _y)
{
x = _x;
y = _y;
}
void Get(double &_x,double &_y)
{
_x = x;
_y = y;
}
bool operator == (const Point& _point)
{
return (doubleCmp(x - _point.x) == 0 ) && (doubleCmp(y - _point.y) == 0);
}
friend Point operator - (const Point& _p1,const Point& _p2)
{
return Point(_p1.x - _p2.x,_p1.y - _p2.y);
}
friend istream& operator >> (istream& in ,Point& p)
{
in >> p.x >> p.y;
return in;
}
friend ostream& operator << (ostream& out, Point& p)
{
out <<"(" <<p.x <<","<< p.y<<")";
return out;
}
};
class VectorCalculator
{
public:
static double CrossMul(const Point& p1,const Point& p2)
{
return (p1.GetX() * p2.GetY() - p2.GetX() * p1.GetY());
}
static double PointMul(const Point& p1,const Point& p2)
{
return (p1.GetX() * p2.GetX() + p1.GetY() * p2.GetY());
}
};
inline double Dist(const Point& p1,const Point& p2)
{
return sqrt((p1.GetX() - p2.GetX())*(p1.GetX() - p2.GetX()) + (p1.GetY() - p2.GetY())*(p1.GetY() - p2.GetY()));
}
inline double DistSquare(const Point& p1,const Point& p2)
{
return ((p1.GetX() - p2.GetX())*(p1.GetX() - p2.GetX()) + (p1.GetY() - p2.GetY())*(p1.GetY() - p2.GetY()));
}
Point minPoint;
bool PointCmp(const Point& p1,const Point& p2)
{
int s = doubleCmp(VectorCalculator::CrossMul(p1 - minPoint,p2 - minPoint));
if(s > 0)
return true;
else if(s == 0)
{
double dist1 = Dist(p1,minPoint);
double dist2 = Dist(p2,minPoint);
return dist1 < dist2;
}
else
{
return false;
}
}
void Graham(Point *_pointSet,Point* _stacks,const int _size,int &len)
{
//1.select the p0 : Y-X mininum
int minId = 0;
for(int i = 1; i < _size; ++i)
{
if( (_pointSet[i].GetY() < _pointSet[minId].GetY() ) ||
((_pointSet[i].GetY() == _pointSet[minId].GetY()) &&
(_pointSet[i].GetX() < _pointSet[minId].GetX() )))
{
minId = i;
}
}
//2.swap the begin point and the p0
swap(_pointSet[0],_pointSet[minId]);
minPoint = _pointSet[0];
//3. sort the set
sort(_pointSet+1,_pointSet + _size,PointCmp);
//4.make a stack
int top = -1;
_stacks[++top] = _pointSet[0];
_stacks[++top] = _pointSet[1];
_stacks[++top] = _pointSet[2];
for(int i = 3; i < _size; ++i)
{
//while nonleft turn
while(VectorCalculator::CrossMul(_stacks[top] - _pointSet[i],_stacks[top-1] - _pointSet[i]) >0)
{
--top;
}
//push
_stacks[++top] = _pointSet[i];
}
len = top + 1;
}
Point points[50005];
Point pntStack[50005];
bool IsProjectTo(const Point& a,const Point &b,const Point &_pro)
{
if(doubleCmp(VectorCalculator::PointMul(_pro-b,a-b)) > 0)
{
if(doubleCmp(VectorCalculator::PointMul(_pro-a,b-a)) > 0)
return true;
}
return false;
}
Point CalCenter(Point* p,int _size)
{
double area = 0;
Point center;
center.Set(0,0);
for (int i = 0; i < _size-1; i++)
{
double cross = VectorCalculator::CrossMul(p[i],p[i+1]);
area += cross/2.0;
center.x += (cross) * (p[i].x + p[i+1].x);
center.y += (cross) * (p[i].y + p[i+1].y);
}
double cross = VectorCalculator::CrossMul(p[_size-1],p[0]);
area += cross/2.0;
center.x += (cross) * (p[_size-1].x + p[0].x);
center.y += (cross) * (p[_size-1].y + p[0].y);
center.x /= 6*area;
center.y /= 6*area;
return center;
}
void Test()
{
int size;
scanf("%d",&size);
double x,y;
for(int i = 0; i < size; ++i)
{
scanf("%lf %lf",&x,&y);
points[i].SetX(x);
points[i].SetY(y);
}
int len = 0;
Point center = CalCenter(points,size);
Graham(points,pntStack,size,len);
int cnt = 0;
for(int i = 0; i < len - 1; ++i)
{
if(IsProjectTo(pntStack[i],pntStack[i+1],center))
++cnt;
}
if(IsProjectTo(pntStack[len-1],pntStack[0],center))
++cnt;
printf("%d\n",cnt);
}
int main()
{
int testcase = 0;
scanf("%d",&testcase);
for(int i = 0; i < testcase; ++i)
{
Test();
}
return 0;
}posted on 2010-11-11 13:41
bennycen 阅读(413)
评论(1) 编辑 收藏 引用 所属分类:
算法题解