pku1569Myacm Triangles

作者在 2010-08-06 14:36:21 发布以下内容
题目:pku1569
代码:计算几何(点在三角形内部)+枚举
// the number of monuments: at least 4, and at most 15

#include <iostream>
#include <cmath>
using namespace std;
const double eps=1e-10;
struct point
{   double x,y;  };
typedef point triangle[3];

//===================================
//判断点p是否在三角形内部
double triangle_area(triangle t)  
{  
    return fabs(t[0].x*t[1].y+t[1].x*t[2].y+t[2].x*t[0].y
                -t[1].x*t[0].y-t[2].x*t[1].y-t[0].x*t[2].y)/2;  
}
bool same (double x,double y)
{  return fabs(x-y)<eps ;   }
bool is_in_triangle(point p,triangle t)
{  
    triangle tmp;  double area=0;   int i,j;
    for (i=0; i<=2; i++)
    {  for (j=0; j<=2; j++)
         if (i==j) tmp[j]=p; else tmp[j]=t[j];
       area=area+triangle_area(tmp);
    }
    return same(area,triangle_area(t));    
}
//====================================
bool samepoint(point a,point b)
{
    if(fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps)return true;
    return false;
}
int main(int argc, char *argv[])
{
    point p[20];
    triangle t;
    int n,i,j,k,temp;
    char ch,ans[3];
    double x,y,area;
    while(cin>>n&&n)
    {
        for(i=0;i<n;i++)
        {
            cin>>ch>>x>>y;
            p[ch-'A'].x=x;p[ch-'A'].y=y;
        }

        area=0;
        for(i=0;i<n;i++)
           for(j=i+1;j<n;j++)
           {
                if(samepoint(p[i],p[j]))continue;
                 for(k=j+1;k<n;k++)
                 {
                      if(samepoint(p[i],p[k])||samepoint(p[j],p[k]))continue;
                      t[0]=p[i];t[1]=p[j];t[2]=p[k];
                      for(temp=0;temp<n;temp++)
                         if(is_in_triangle(p[temp],t)&&temp!=i&&temp!=j&&temp!=k)break;
                   if(temp==n&&triangle_area(t)>area)
                   {
                          area=triangle_area(t);ans[0]='A'+i;ans[1]='A'+j;ans[2]='A'+k;
                   }
              }
             }
          printf("%c%c%c\n",ans[0],ans[1],ans[2]);
            
    }
    system("pause");
    return 0;
}
默认分类 | 阅读 884 次
文章评论,共0条
游客请输入验证码
最新评论