首页 > ACM题库 > HDU-杭电 > hdu 2183 奇数阶魔方(II)-计算几何-[解题报告]C++
2013
12-30

hdu 2183 奇数阶魔方(II)-计算几何-[解题报告]C++

奇数阶魔方(II)

问题描述 :

1 ,2, 3, …,n^2 这n^2 个数 排成n*n 方阵 每行每列每条对角线上的n个数字之和s相等,
s=n(n*n+1)/2,奇数阶魔方可由菱形转变成
n=3,5时如下
3
*********1
******4******2
***7*****5******3
******8******6
*********9
4 9 2
3 5 7
8 1 6
5
*******************1
***************6*******2
**********11*******7*******3
******16*******12*******8*******4
**21******17******13*******9*******5
******22*******18*****14******10
**********23*******19******15
**************24******20
******************25
11 24 7 20 3
4 12 25 8 16
17 5 13 21 9
10 18 1 14 22
23 6 19 2 15

输入:

输入奇数 3<=n<=21. n=0退出

输出:

输入奇数 3<=n<=21. n=0退出

样例输入:

7
0

样例输出:

  22  47  16  41  10  35   4
   5  23  48  17  42  11  29
  30   6  24  49  18  36  12
  13  31   7  25  43  19  37
  38  14  32   1  26  44  20
  21  39   8  33   2  27  45
  46  15  40   9  34   3  28

题目:http://acm.hit.edu.cn/hoj/problem/view?id=2183

本题核心是求任意多边形的面积。

我们可以用叉积来求。任取一点,顺时针取相邻两点,与这点组成两个向量,进行叉积。顺时针一周求得的所有叉积和求反除以二即是多边形的面积。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;

struct Point
{
    double x;
    double y;
};
Point p[100000];

double cross(Point O,Point A,Point B)
{
    return (A.x - O.x) *  (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int n;
    double vol;
    while(scanf(" %d",&n)!=EOF && n>=3)
    {
        p[0].x = p[0].y = 0;
        for(int i=1;i<=n;i++)
        {
            scanf(" %lf %lf",&p[i].x,&p[i].y);
        }
        scanf(" %lf",&vol);
        p[n+1].x = p[1].x;
        p[n+1].y = p[1].y;
        double area = 0;
        for(int i=1;i<=n;i++)
        {
            area += cross(p[0],p[i],p[i+1]);
        }
        area = -area;
        area /=2;
        double len;
        len = vol/area;
        printf("BAR LENGTH: %.2lf\n",len);
    }
}

解题转自:http://blog.csdn.net/niuox/article/details/8592852