Pagini recente » Cod sursa (job #3202028) | Cod sursa (job #2583065) | Cod sursa (job #1771048) | Cod sursa (job #1250066) | Cod sursa (job #2301469)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
const double eps = 1e-5;
struct Punct
{
Punct(double x = 0.0, double y = 0.0)
{
this->x = x;
this->y = y;
}
double x, y;
};
double det(const Punct &a, const Punct &b, const Punct &c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
int sign(double x)
{
if(x > eps)
return 1;
if(x < -eps)
return -1;
return 0;
}
Punct intersect(const Punct &a, const Punct &b, const Punct &c, const Punct &d)
{
double a1 = b.y - a.y;
double b1 = a.x - b.x;
double c1 = b.x*a.y - a.x*b.y;
double a2 = d.y - c.y;
double b2 = c.x - d.x;
double c2 = d.x*c.y - c.x*d.y;
double div = a1*b2 - a2*b1;
double x = (b1*c2 - b2*c1) / div;
double y = (a2*c1 - a1*c2) / div;
return Punct(x, y);
}
void CutPol(const Punct &a, const Punct &b, vector<Punct> &pol)
{
vector<Punct> ret;
int s1, s2;
Punct I;
for(int i = 0; i < pol.size(); ++i)
{
auto &cur = pol[i], &urm = pol[(i+1) % pol.size()];
s1 = sign(det(cur, a, b)), s2 = sign(det(urm, a, b));
if(s1 * s2 < 0)
{
I = intersect(cur, urm, a, b);
if(s1 > 0)
{
ret.push_back(cur);
ret.push_back(I);
}
else
{
ret.push_back(I);
ret.push_back(urm);
}
}
else if(s1 >= 0)
ret.push_back(pol[i]);
}
pol = ret;
}
double GetArea(const vector<Punct> &pol)
{
double ret = 0;
Punct O(0, 0);
for(int i = 1; i < pol.size(); ++i)
ret += det(O, pol[i-1], pol[i]);
ret += det(O, pol.back(), pol[0]);
ret /= 2;
return ret;
}
int main()
{
ifstream in("camera.in");
int n;
in >> n;
vector<Punct> v(n);
for(auto &p:v)
in >> p.x >> p.y;
in.close();
double minX = v[0].x, minY = v[0].y, maxX = v[0].x, maxY = v[0].y;
for(int i = 1; i < n; ++i)
{
minX = min(minX, v[i].x);
minY = min(minY, v[i].y);
maxX = max(maxX, v[i].x);
maxY = max(maxY, v[i].y);
}
if(GetArea(v) < 0)
reverse(v.begin(), v.end());
vector<Punct> pol;
pol.push_back(Punct(minX, minY));
pol.push_back(Punct(maxX, minY));
pol.push_back(Punct(maxX, maxY));
pol.push_back(Punct(minX, maxY));
for(int i = 1; i < n; ++i)
CutPol(v[i-1], v[i], pol);
CutPol(v[n-1], v[0], pol);
ofstream out("camera.out");
out << fixed << setprecision(2) << abs(GetArea(pol)) << "\n";
out.close();
return 0;
}