博客首页 注册 建议与交流 排行榜 加入友情链接
推荐 投诉 搜索: 帮助

Linuxer William

帮忙点下上面的广告看是不是能有钱钱阿!

   zuii.cublog.cn
关于作者  
姓名:William Cheung
职业:Linuxer
年龄:比小学生老多了
位置:四川
个性介绍:比较适合做程序员

    QQ:412430450
    MSN: williamzuii@163.com
    百度Hi:zuii

我的分类  




百度之星2009初赛第二轮题二------圆内五角星

问题背景

如图,一个半径为1的圆周上有5个点。按角度制给出5个点的极角Ai (0<=Ai<360, i=1..5)。按下图的方法连成一个五角星, 计算圆被切割成的11个部分面积的方差。


具体地说, 假定11个区域的面积分别为S1,S2, ..., S11,那么面积的均值计算方法为:
M = (S1+S2+...+S11 ) / 11

面积的方差计算方法为:
D = ((S1-M)2 + (S2-M)2 + ... + (S11-M)2) / 11

输入格式

输入仅一行,包含5个[0,359]内的互不相等的整数。

输出格式

输出仅一行,包含一个实数,即各部分面积的方差。输出保留小数点后4位。

样例输入

0 144 72 288 216

样例输出

0.0647

 发表于: 2008-06-01,修改于: 2008-06-01 14:10 已浏览225次,有评论2条 推荐 投诉

  网友评论
  weolar 时间:2008-06-04 00:02:10 IP地址:117.22.50.★
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define Pi 3.1415926535898

//两线段交点
void GetCrossPoint(double *x, double *y, double x1, double y1, double x2,
  double y2, double x3, double y3, double x4, double y4) //四点交点坐标
{
  //1 3 一条直线,2,4一条

    double x_,y_;
    /*
  if (x1==x3)
  {
     x_=x1;
     y_=(x1-x4)*(y2-y4)/(x2-x4)+y4;
  }
  if (x1==x3)
  {
     x_=x2;
     y_=(x2-x1)*(y3-y1)/(x3-x1)+y1;
  }
  else
  {
   x_ = ((y1 - y2) - x1 *(y3 - y1) / (x3 - x1) + x2 *(y4 - y2) / (x4 - x2)
    ) / ((y4 - y2) / (x4 - x2) - (y3 - y1) / (x3 - x1));
   y_ = (x_ - x2)*(y4 - y2) / (x4 - x2) + y2;
  }
  *x = x_;
   *y = y_;
*/
   //根据两点式化为标准式,进而求线性方程组
   double tempLeft,tempRight;

   //求x坐标
   tempLeft = (x2 - x4) * (y1 - y3) - (x3 - x1) * (y4 - y2);
   tempRight = (y1 - y4) * (x3 - x1) * (x2 - x4) + x4 * (y2 - y4) * (x3 - x1) - x1 * (y3 - y1) * (x2 - x4);
   x_ =tempRight /tempLeft;
   //求y坐标
   tempLeft = (x1 - x3) * (y2 - y4) - (y3 - y1) * (x4 - x2);
   tempRight = y3 * (x1 - x3) * (y2 - y4) + (x2- x3) * (y2 - y4) * (y1 - y3) - y2 * (x4 - x2) * (y3 - y1);
   y_ =tempRight / tempLeft;
   *x = x_;
   *y = y_;

}
//由三点坐标得出面积
double GetAreaByThirePoint(double x1, double y1, double x2, double y2, double x3,double y3) 
{
  double a = x2 - x1;
  double b = y2 - y1;
  double c = x3 - x1;
  double d = y3 - y1;
  return 0.5 *fabs(a *d - b * c);
}

//排序
void BubbleSort(int *pData, int Count)
{
  int iTemp;
  for (int i = 1; i < Count; i++)
  {
    for (int j = Count - 1; j >= i; j--)
    {
      if (pData[j] < pData[j - 1])
      {
        iTemp = pData[j - 1];
        pData[j - 1] = pData[j];
        pData[j] = iTemp;
      }
    }
  }
}

int main()
{
  int N,  *b;
  double *a;
  int i = 0, j = 0;
  int sum = 0;

  N = 5;
  //scanf("%d", &N);
  b = (int*)malloc(5 *sizeof(int*));//角度制下的输入角度
  a = (double*)malloc(5 *sizeof(double*));//被转化后的弧度

  ///--------------------0 144 72 288 216

  //b[0]=1; b[1]=73; b[2]=145; b[3]=289; b[4]=217;
 /* b[0]=90; b[1]=270; b[2]=45; b[3]=315; b[4]=0;
  //Max=23;
  
  for (i = 0; i < 5; i++)
  {
      b[i] = b[i] -1;
  }
  */
   for (i = 0; i < 5; i++)
  {
    scanf("%d", b + i);
  }
  //三角形面积:
  BubbleSort(b, 5);
  for (i = 0; i < 5; i++)
  {
    a[i] = b[i] *2 * Pi / 360;
  }
  //double aa = GetAreaByThirePoint(0, 0, 1, 0, 0, 1);
  double v1, v2;
  GetCrossPoint(&v1, &v2, 0, 0, 1, 0, 1, 1, 0, 1);
  GetCrossPoint(&v1, &v2, 0, 0, 1, 0, 1, 1, 0, 1);

  double x[6], y[6], Trigon[6], Fan[6];
  x[0] = cos(a[0]); y[0] = sin(a[0]);
  x[1] = cos(a[1]); y[1] = sin(a[1]);
  x[2] = cos(a[2]); y[2] = sin(a[2]);
  x[3] = cos(a[3]); y[3] = sin(a[3]);
  x[4] = cos(a[4]); y[4] = sin(a[4]);
  double Left_x, Left_y, Right_x, Righ_y;
  for (i = 0; i < 5; i++)
  {
    GetCrossPoint(&Left_x, &Left_y, x[(0+i) % 5], y[(0+i) % 5], x[(1+i) % 5], y[(1+i) % 5], x[(2+i) % 5], y[(2+i) % 5], x[(4+i) % 5], y[(4+i) % 5]);
    GetCrossPoint(&Right_x, &Righ_y, x[(0+i) % 5], y[(0+i) % 5], x[(1+i) % 5], y[(1+i) % 5], x[(3+i) % 5], y[(3+i) % 5], x[(4+i) % 5], y[(4+i) % 5]);
    
    Trigon[i] = GetAreaByThirePoint(x[(i) % 5], y[(i) % 5], Left_x, Left_y, Right_x,Righ_y);
    double temp = a[i % 5] - a[(1+i) % 5];
    if (temp > Pi)
    {
      temp = Pi*2 - temp;
    }
    else
      temp =  - 1 * temp;
    Fan[i] = 0.5 *(temp) - GetAreaByThirePoint(0.0, 0.0, x[(i) % 5], y[(i) % 5],x[(1+i) % 5], y[(1+i) % 5]) + GetAreaByThirePoint(Left_x, Left_y, x[(i) % 5], y[(i) % 5], x[(1+i) % 5], y[(1+i) % 5]);
  } //求三角,弓形面积
  double AllEquation = 0.0, Alltrigon = 0.0;
  double LastArea = 0.0;//最后的中心的面积
  for (i = 0; i < 5; i++)
  {
    LastArea += Trigon[i] + Fan[i];
  } //求中心面积

  LastArea = Pi - LastArea;

  for (i = 0; i < 5; i++)
  {
    Alltrigon += (Trigon[i] - Pi / 11)*(Trigon[i] - Pi / 11);
    AllEquation += (Fan[i] - Pi / 11)*(Fan[i] - Pi / 11);
  }

  double result = (Alltrigon + AllEquation + (LastArea - Pi / 11)*(LastArea -Pi / 11)) / 11;
  result = (double)((int)(result*10000+0.5))/10000.0;
  printf("%0.4f\n", result);
  return 0;
}

  zuii 时间:2008-06-05 23:43:23 IP地址:124.161.158.★
LS厉害~~
几何方面的我直接放弃,呵呵~~
算法方面还可以做一下。


  发表评论



Copyright © 2001-2006 ChinaUnix.net All Rights Reserved

感谢所有关心和支持过ChinaUnix的朋友们
页面生成时间:0.18915

京ICP证041476号