Pagini recente » Cod sursa (job #1798915) | Cod sursa (job #986241)
Cod sursa(job #986241)
#include <fstream>
#include <utility>
#include <cmath>
#include <iomanip>
#define maxn 2001
#define inf 100001
#define eps 1e-6
#define x first
#define y second
using namespace std;
ifstream fin ("camera.in");
ofstream fout ("camera.out");
typedef pair<double,double> point;
point p[maxn],temp[maxn],v[maxn];
int sgn[maxn];
int t,n,m;
int what_side (double a, double b, double c, point P)
{
double d = a*P.x + b*P.y +c;
if (d<-eps) return -1;
if (d>eps) return 1;
return 0;
}
void get_coefficients (point p1, point p2, double &a, double &b, double &c)
{
a = p2.y - p1.y;
b = p1.x - p2.x;
c = p2.x*p1.y - p1.x*p2.y;
}
point intersection (double a1, double b1, double c1, point p1, point p2)
{
double a2,b2,c2; point P;
get_coefficients (p1,p2,a2,b2,c2);
double det = a1*b2-a2*b1;
P.x = (b1*c2-b2*c1)/det;
P.y = (a2*c1-a1*c2)/det;
return P;
}
double area ()
{
double A=0;
for (int i=1; i<=t; ++i)
{
int ii; i==t ? ii=1 : ii=i+1;
A += p[i].x*p[ii].y-p[ii].x*p[i].y;
}
return fabs(A/2);
}
int main()
{
fin>>n;
for (int i=1; i<=n; ++i)
fin>>v[i].x>>v[i].y;
p[1].x=inf; p[1].y=inf;
p[2].x=inf; p[2].y=-inf;
p[3].x=-inf; p[3].y=-inf;
p[4].x=-inf; p[4].y=inf;
t=4;
for (int i=1; i<=n; ++i)
{
int ii; i==n ? ii=1 : ii=i+1;
double a,b,c;
get_coefficients (v[i],v[i+1],a,b,c);
for (int j=1; j<=t; ++j)
sgn[j] = what_side (a,b,c,p[j]);
int te=0;
for (int j=1; j<=t; ++j)
{
int jj; j==t ? jj=1 : jj=j+1;
if (sgn[j]>=0 && sgn[jj]>=0) temp[++te]=p[j];
else if (sgn[j]<0 && sgn[jj]>=0) temp[++te]= intersection (a,b,c,p[j],p[jj]);
else if (sgn[j]>=0 && sgn[jj]<0) temp[++te]=p[j],temp[++te]= intersection (a,b,c,p[j],p[jj]);
}
t=te;
for (int j=1; j<=t; ++j) p[j]=temp[j];
}
double A=area();
fout<<fixed<<setprecision(2)<<A;
}