/****************************/
/* 抽象クラス */
/* coded by Y.Suganuma */
/****************************/
#include <iostream>
#include <math.h>
#include <stdlib.h>
/****************/
/* クラスFigure */
/****************/
class Figure {
public:
double s; // 図形の面積
virtual void input() = 0; // データの入力，純粋仮想関数
virtual void menseki() = 0; // 面積の計算，純粋仮想関数
void print(int sw) // 結果の出力
{
if (sw == 0)
std::cout << " 与えられた楕円の面積は " << s << " です\n";
else
std::cout << "与えられた多角形の面積は " << s << " です\n";
}
};
/*****************/
/* クラスEllipse */
/*****************/
class Ellipse : public Figure {
double a, b; // 楕円の長径と短径
public:
void input() // データの入力
{
std::cout << "楕円の長径は？ ";
std::cin >> a;
std::cout << "楕円の短径は？ ";
std::cin >> b;
}
void menseki() // 楕円の面積
{
s = 4.0 * atan(1.0) * a * b;
}
};
/*****************/
/* クラスPolygon */
/*****************/
class Polygon : public Figure {
int n; // 点の数
int *m; // 点の番号
double **p; // 各点の座標
double men(int, double **, int *);
double sankaku(int, int, int *, double **);
int check1(int, int, int *, double **);
int check2(int, int, int *, double **);
public:
// コンストラクタ
Polygon (int n1)
{
if (n1 < 3) {
std::cout << "３点以上与えてください\n";
exit(1);
}
else {
n = n1;
m = new int [n];
p = new double * [n];
for (int i1 = 0; i1 < n; i1++)
p[i1] = new double [2];
}
}
// デストラクタ
~Polygon ()
{
if (n > 0) {
for (int i1 = 0; i1 < n; i1++)
delete [] p[i1];
delete [] p;
delete [] m;
}
}
// データの入力
void input()
{
std::cout << "各点の座標の入力（反時計回り）\n";
for (int i1 = 0; i1 < n; i1++) {
std::cout << " " << i1+1 << " 番目の点のｘ座標は？ ";
std::cin >> p[i1][0];
std::cout << " " << i1+1 << " 番目の点のｙ座標は？ ";
std::cin >> p[i1][1];
}
}
// 多角形の面積
void menseki()
{
for (int i1 = 0; i1 < n; i1++)
m[i1] = i1;
s = men(n, p, m);
}
};
/******************************/
/* 多角形の面積を再帰的に計算 */
/* n : 点の数 */
/* p : 点の座標 */
/* m : 点番号 */
/* return : 面積 */
/******************************/
double Polygon::men(int n, double **p, int *m)
{
double s = 0.0;
if (n == 3) // 三角形
s = sankaku(n, 0, m, p);
else {
int sw1 = 0;
for (int i1 = 0; i1 < n && sw1 == 0; i1++) {
int sw = check1(n, i1, m, p); // 多角形の中？
if (sw == 0) {
sw = check2(n, i1, m, p); // 中に他の点がある？
if (sw == 0) {
s = sankaku(n, i1, m, p); // i1から始まる三角形
for (int i2 = i1+1; i2 < n-1; i2++) // 点を除く
m[i2] = m[i2+1];
s += men(n-1, p, m); // (n-1)この点からなる多角形
sw1 = 1;
}
}
}
}
return s;
}
/***********************/
/* 三角形の面積の計算 */
/* n : 点の数 */
/* k : 開始点番号 */
/* m : 点番号 */
/* p : 点の座標 */
/* return : 面積 */
/***********************/
double Polygon::sankaku(int n, int k, int *m, double **p)
{
int k1 = m[k];
int k2 = (k == n-1) ? m[0] :m[k+1];
int k3;
if (k < n-2)
k3 = m[k+2];
else
k3 = (k == n-2) ? m[0] : m[1];
double x1 = p[k2][0] - p[k1][0];
double y1 = p[k2][1] - p[k1][1];
double r1 = sqrt(x1 * x1 + y1 * y1);
double t1 = atan2(y1, x1);
x1 = p[k3][0] - p[k1][0];
y1 = p[k3][1] - p[k1][1];
double r2 = sqrt(x1 * x1 + y1 * y1);
double t2 = atan2(y1, x1);
double t3 = t2 - t1;
double s = fabs(0.5 * r1 * r2 * sin(t3));
return s;
}
/****************************************/
/* 三角形が多角形の内部か否かのチェック */
/* n : 点の数 */
/* k : 開始点番号 */
/* m : 点番号 */
/* p : 点の座標 */
/* return : =0 : 内部である */
/* =1 : 内部でない */
/****************************************/
int Polygon::check1(int n, int k, int *m, double **p)
{
double pi = 4.0 * atan2(1.0, 1.0);
int k1 = m[k];
int k2 = (k == n-1) ? m[0] :m[k+1];
int k3;
if (k < n-2)
k3 = m[k+2];
else
k3 = (k == n-2) ? m[0] : m[1];
double x1 = p[k3][0] - p[k1][0];
double y1 = p[k3][1] - p[k1][1];
double t1 = atan2(y1, x1);
x1 = p[k2][0] - p[k1][0];
y1 = p[k2][1] - p[k1][1];
double t2 = atan2(y1, x1);
double t3 = t2 - t1;
if (t3 > pi)
t3 -= 2.0 * pi;
else {
if (t3 < -pi)
t3 += 2.0 * pi;
}
int sw = 0;
if (t3 > 0.0)
sw = 1;
return sw;
}
/************************************************/
/* 三角形内に他の頂点が存在するか否かのチェック */
/* n : 点の数 */
/* k : 開始点番号 */
/* m : 点番号 */
/* p : 点の座標 */
/* return : =0 : 存在しない */
/* =1 : 存在する */
/************************************************/
int Polygon::check2(int n, int k, int *m, double **p)
{
double pi = 4.0 * atan2(1.0, 1.0);
int k1 = m[k];
int k2 = (k == n-1) ? m[0] :m[k+1];
int k3, sw = 0;
if (k1 < n-2)
k3 = m[k+2];
else
k3 = (k == n-2) ? m[0] : m[1];
double x1 = p[k2][0] - p[k1][0];
double y1 = p[k2][1] - p[k1][1];
double t10 = atan2(y1, x1);
x1 = p[k3][0] - p[k2][0];
y1 = p[k3][1] - p[k2][1];
double t11 = atan2(y1, x1);
x1 = p[k1][0] - p[k3][0];
y1 = p[k1][1] - p[k3][1];
double t12 = atan2(y1, x1);
for (int i1 = 0; i1 < n && sw == 0; i1++) {
if (i1 != k1 && i1 != k2 && i1 != k3) {
x1 = p[m[i1]][0] - p[k1][0];
y1 = p[m[i1]][1] - p[k1][1];
double t2 = atan2(y1, x1);
double t3 = t2 - t10;
if (t3 > pi)
t3 -= 2.0 * pi;
else {
if (t3 < -pi)
t3 += 2.0 * pi;
}
if (t3 > 0.0) {
x1 = p[m[i1]][0] - p[k2][0];
y1 = p[m[i1]][1] - p[k2][1];
double t2 = atan2(y1, x1);
t3 = t2 - t11;
if (t3 > pi)
t3 -= 2.0 * pi;
else {
if (t3 < -pi)
t3 += 2.0 * pi;
}
if (t3 > 0.0) {
x1 = p[m[i1]][0] - p[k3][0];
y1 = p[m[i1]][1] - p[k3][1];
t2 = atan2(y1, x1);
t3 = t2 - t12;
if (t3 > pi)
t3 -= 2.0 * pi;
else {
if (t3 < -pi)
t3 += 2.0 * pi;
}
if (t3 > 0.0)
sw = 1;
}
}
}
}
return sw;
}
/*************/
/* main 関数 */
/*************/
int main()
{
/*
楕円
*/
Ellipse e1;
e1.input();
e1.menseki();
e1.print(0);
/*
多角形
*/
int n;
std::cout << "点の数は？ ";
std::cin >> n;
Polygon p1(n);
p1.input();
p1.menseki();
p1.print(1);
return 0;
}