Pagini recente » Cod sursa (job #94893) | Monitorul de evaluare | Cod sursa (job #750253) | Cod sursa (job #3220853) | Cod sursa (job #1412437)
#include <iostream>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
const double eps = 1e-12;
const int max_int = 100010;
ifstream F("camera.in");
ofstream G("camera.out");
pair<double,double> nowhere = make_pair(-max_int*2,-max_int*2);
#define x first
#define y second
int n;
vector< pair<double,double> > polygon,new_polygon;
vector< pair<double,double> > points;
double area(vector< pair<double,double> > v)
{
double ans = 0;
for (int i=0;i<int(v.size())-1;++i)
ans += v[i].x * v[i+1].y - v[i+1].x * v[i].y;
return ans/2;
}
int sign(pair<double,double> p1,pair<double,double> p2,pair<double,double> p3)
{
double a = p1.y - p2.y;
double b = p2.x - p1.x;
double c = - p2.x * p1.y - p1.x * p2.y;
if ( p3.x * a + p3.y * b + c < 0 )
return -1;
return 1;
}
pair<double,double> intersection(pair<double,double> p1,pair<double,double> p2,pair<double,double> p3,pair<double,double> p4)
{
double a1 = p1.y - p2.y;
double b1 = p2.x - p1.x;
double c1 = - p1.y * p2.x + p2.y * p1.x;
double a2 = p3.y - p4.y;
double b2 = p4.x - p3.x;
double c2 = - p3.y * p4.x + p4.y * p3.x;
double d = a1*b2 - a2*b1;
if ( fabs(d) < eps )
return nowhere;
double xx = -(b2*c1-b1*c2)/d;
double yy = b1 != 0 ? (- a1 * xx - c1) / b1 : (- a2 * xx - c2) / b2;
return make_pair(xx,yy);
}
int main()
{
F>>n;
for (int i=1,x,y;i<=n;++i)
{
F>>x>>y;
points.push_back(make_pair(x,y));
}
points.push_back(points[0]);
int sgn = area(points) > 0 ? 1 : -1;
polygon.push_back(make_pair(-max_int,max_int));
polygon.push_back(make_pair(max_int,max_int));
polygon.push_back(make_pair(max_int,-max_int));
polygon.push_back(make_pair(-max_int,-max_int));
polygon.push_back(make_pair(-max_int,max_int));
for (int i=0;i<n;++i)
{
new_polygon = vector< pair<double,double> >();
for (int j=0;j<int(polygon.size())-1;++j)
{
int sign1 = sign(points[i],points[i+1],polygon[j]);
int sign2 = sign(points[i],points[i+1],polygon[j+1]);
if ( sign1 == sgn && sign2 == sgn )
new_polygon.push_back( polygon[j+1] );
if ( sign1 == sgn && sign2 == -sgn )
{
pair<double,double> what = intersection(points[i],points[i+1],polygon[j],polygon[j+1]);
if ( -max_int <= what.x && what.x <= max_int && -max_int <= what.y && what.y <= max_int ) new_polygon.push_back( what );
//if ( what != nowhere ) new_polygon.push_back( what );
}
if ( sign1 == -sgn && sign2 == sgn )
{
pair<double,double> what = intersection(points[i],points[i+1],polygon[j],polygon[j+1]);
if ( -max_int <= what.x && what.x <= max_int && -max_int <= what.y && what.y <= max_int ) new_polygon.push_back( what );
//if ( what != nowhere ) new_polygon.push_back( what );
new_polygon.push_back( polygon[j+1] );
}
if ( new_polygon.size() > 1 )
{
vector<pair<double,double> >::iterator it = new_polygon.end(); --it;--it;
if ( new_polygon.back() == *it )
new_polygon.pop_back();
}
}
polygon = new_polygon;
polygon.push_back(polygon[0]);
}
double ans = area(polygon);
if ( ans < 0 ) ans = -ans;
G<<fixed<<setprecision(3)<<ans<<'\n';
}