Pagini recente » Cod sursa (job #1786196) | Cod sursa (job #882724) | Cod sursa (job #284627) | Cod sursa (job #1733516) | Cod sursa (job #600894)
Cod sursa(job #600894)
# include <cstdio>
# include <cmath>
# include <vector>
using namespace std;
# define x first
# define y second
# define pb push_back
# define mp make_pair
typedef double db;
typedef pair <int, int> pr;
typedef pair <db, db> PR;
const char *FIN = "camera.in", *FOU = "camera.out";
const int MAX = 2005;
const db eps = 1e-6, oo = 1e+6;
pr V[MAX];
vector <PR> vec, next;
vector <int> aux;
int N;
inline int semn (pair <db, PR> Cf, PR XY) {
db Z = Cf.x * XY.x + Cf.y.x * XY.y + Cf.y.y;
return (Z < -eps ? -1 : (Z > eps ? 1 : 0));
}
inline pair <db, PR> get_coef (PR A, PR B) {
return mp (A.y - B.y, mp (B.x - A.x, A.x * B.y - B.x * A.y));
}
PR intersect (pair <db, PR> Cf, PR X, PR Y) {
pair <db, PR> XX = get_coef (X, Y);
double determin = Cf.x * XX.y.x - XX.x * Cf.y.x;
if (fabs (determin) < eps)
return mp (-oo, -oo);
return mp ((Cf.y.x * XX.y.y - XX.y.x * Cf.y.y) / determin, (XX.x * Cf.y.y - Cf.x * XX.y.y) / determin);
}
db get_sol (void) {
vec.clear (), aux.clear ();
vec.pb (mp (-oo, -oo));
vec.pb (mp (-oo, +oo));
vec.pb (mp (+oo, +oo));
vec.pb (mp (+oo, -oo));
for (int i = 0; i < N; ++i, vec = next) {
next.clear (), aux.resize (vec.size () + 1);
pair <db, PR> Cf = get_coef (V[i], V[i + 1]);
for (size_t j = 0; j < vec.size (); ++j)
aux[j] = semn (Cf, vec[j]);
aux[vec.size ()] = aux[0];
for (size_t j = 0; j < vec.size (); ++j) {
PR AUX = vec[ (j + 1) % static_cast <int> (vec.size ()) ];
if (aux[j] <= 0 && aux[j + 1] <= 0)
next.pb (AUX);
if (aux[j] <= 0 && aux[j + 1] > 0)
next.pb (intersect (Cf, vec[j], AUX));
if (aux[j] > 0 && aux[j + 1] <= 0) {
next.pb (intersect (Cf, vec[j], AUX));
next.pb (AUX);
}
}
}
double sol = 0;
vec.pb (vec[0]);
for (size_t i = 0; i + 1 < vec.size (); ++i)
sol += vec[i].x * vec[i + 1].y - vec[i + 1].x * vec[i].y;
return fabs (sol * 0.5);
}
int main (void) {
freopen (FIN, "r", stdin);
scanf ("%d", &N);
for (int i = 0; i < N; ++i)
scanf ("%d %d", &V[i].x, &V[i].y);
V[N] = V[0];
double sol = get_sol ();
if (fabs (sol) < eps) {
for (int i = 0, j = N; i < j; ++i, --j)
swap (V[i], V[j]);
sol = get_sol ();
}
fprintf (fopen (FOU, "w"), "%.2lf", sol);
}