作者在 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;
}
#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;
}