Pagini recente » Cod sursa (job #641069) | Cod sursa (job #1708350) | Cod sursa (job #1046772) | Cod sursa (job #2328183) | Cod sursa (job #1691430)
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("camera.in");
ofstream fout("camera.out");
const double INF = 100000.0;
const double eps = 1e-6;
int N, M, P;
int sgn;
struct puncte
{
double x, y;
};
puncte V[2005], A[2005], B[2005];
int cross_panta(puncte A, puncte B, puncte C)
{
double val = (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);
if (fabs(val) < eps)
return 0;
if (val >= eps)
return 1;
if (val <= -eps)
return -1;
}
puncte intersect(puncte A, puncte B, puncte C, puncte D)
{
double a1, b1, c1, a2, b2, c2;
// (y2 - y1) * x + (x1 - x2) * y + (x2 * y1 - x1 * y2) = 0
// a = y2 - y1
// b = x1 - x2
// c = (x2 * y1 - x1 * y2)
a1 = B.y - A.y;
b1 = A.x - B.x;
c1 = B.x * A.y - A.x * B.y;
a2 = D.y - C.y;
b2 = C.x - D.x;
c2 = D.x * C.y - C.x * D.y;
puncte E;
if (fabs((a1 * b2) - (a2 * b1)) < eps)
E.x = (c2 * b1) - (c1 * b2);
else
E.x = ((c2 * b1) - (c1 * b2)) / ((a1 * b2) - (a2 * b1));
if (fabs((a2 * b1) - (a1 * b2)) < eps)
E.y = (a1 * c2) - (a2 * c1);
else
E.y = ((a1 * c2) - (a2 * c1)) / ((a2 * b1) - (a1 * b2));
return E;
}
int arie()
{
long long a = 0;
for (int i = 1; i <= N; ++i)
a += V[i].x * V[i + 1].y - V[i + 1].x * V[i].y;
if (a > 0LL)
return 1;
return -1;
}
int main()
{
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> V[i].x >> V[i].y;
V[N + 1] = V[1];
int a = arie(); // ia sa vedem noi cum sunt punctele
if (a > 0) // punctele sunt in ordine trigonometrica
sgn = -1;
else // punctele nu sunt in ordine trigonometrica(logic, daaaaa)
sgn = 1;
M = 4;
A[1].x = -INF;
A[1].y = -INF;
A[2].x = INF;
A[2].y = -INF;
A[3].x = INF;
A[3].y = INF;
A[4].x = -INF;
A[4].y = INF;
A[5] = A[1];
for (int i = 1; i <= N; ++i)
{
int cur, next;
for (int j = 1; j <= M; ++j)
{
cur = j;
next = j + 1;
int s1 = cross_panta(V[i], V[i + 1], A[cur]);
int s2 = cross_panta(V[i], V[i + 1], A[next]);
if (s1 == sgn && s2 == sgn) // ambele sunt in interior
B[++P] = A[next];
else if (s1 == sgn && s2 != sgn) // cur e in interior, next e afara
B[++P] = intersect(V[i], V[i + 1], A[cur], A[next]);
else if (s1 != sgn && s2 == sgn) // cur e afara, next e in interior
{
B[++P] = intersect(V[i], V[i + 1], A[cur], A[next]);
B[++P] = A[next];
}
}
for (int j = 1; j <= P; ++j)
A[j] = B[j];
A[P + 1] = A[1];
M = P;
P = 0;
}
double sol = 0;
for (int i = 1; i <= M; ++i)
sol += A[i].x * A[i + 1].y - A[i + 1].x * A[i].y;
fout << fixed << setprecision(2) << fabs(sol) / 2.0 << '\n';
fin.close();
fout.close();
return 0;
}