Pagini recente » Cod sursa (job #3133942) | Cod sursa (job #1459119) | Cod sursa (job #3206624) | Cod sursa (job #547377) | Cod sursa (job #2979665)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
#define pii pair <long long, long long>
#define ll long long
ifstream in ("camera.in");
ofstream out ("camera.out");
struct str
{
double x, y;
};
const long long max_size = 2e3 + 3;
const double eps = 1e-7, INF = 1e5 + 1;
str v[max_size];
vector <str> plan, aux;
double arie (str x, str y, str z)
{
return (x.x * (y.y - z.y) + y.x * (z.y - x.y) + z.x * (x.y - y.y));
}
long long sgn (double x)
{
if (x > eps)
{
return 1;
}
if (x < -eps)
{
return -1;
}
return 0;
}
void push (str y1, str y2, str x1, str x2)
{
double difxx = x1.x - x2.x, difxy = x2.y - x1.y, difyx = y1.x - y2.x, difyy = y2.y - y1.y;
double aux1 = (x2.x * x1.y - x1.x * x2.y), aux2 = (y2.x * y1.y - y1.x * y2.y);
double x = (aux2 * difxx - aux1 * difyx) / (difxy * difyx - difxx * difyy), y = (aux1 * difyy - aux2 * difxy) / (difxy * difyx - difxx * difyy);
aux.push_back({x, y});
}
signed main ()
{
long long n;
double arietot = 0;
in >> n;
for (long long i = 1; i <= n; i++)
{
in >> v[i].x >> v[i].y;
}
for (int i = 1; i < n; i++)
{
arietot += arie(v[i], v[i + 1], {0, 0});
}
if (arietot < 0)
{
reverse(v + 1, v + n + 1);
}
v[n + 1] = v[1];
plan.push_back({-INF, -INF});
plan.push_back({INF, -INF});
plan.push_back({INF, INF});
plan.push_back({-INF, INF});
for (long long i = 1; i <= n; i++)
{
for (long long j = 0; j < plan.size(); j++)
{
long long k = j + 1;
if (k == plan.size())
{
k = 0;
}
long long sgn1 = sgn(arie(v[i], v[i + 1], plan[j])), sgn2 = sgn(arie(v[i], v[i + 1], plan[k]));
if (sgn1 * sgn2 == -1)
{
push(plan[j], plan[k], v[i], v[i + 1]);
}
if (sgn2 >= 0)
{
aux.push_back(plan[k]);
}
}
plan = aux;
aux.clear();
}
double ans = 0;
for (long long i = 0; i < plan.size(); i++)
{
//out << plan[i].x << " " << plan[i].y << '\n';
long long j = i + 1;
if (j == plan.size())
{
j = 0;
}
ans += arie(plan[i], plan[j], {0, 0});
}
if (ans < 0)
{
ans = -ans;
}
ans /= 2;
out << fixed << setprecision(2) << ans;
in.close();
out.close();
return 0;
}