Pagini recente » Cod sursa (job #2961008) | Cod sursa (job #2482814) | Monitorul de evaluare | Cod sursa (job #377006) | Cod sursa (job #2339919)
#include <bits/stdc++.h>
using namespace std;
using Point=complex<double>;
const double kEps=1e-9;
double cross(Point a,Point b){return imag(conj(a)*b);}
double det(Point a,Point b,Point c){return cross(b-a,c-a);}
int sgn(double d){return abs(d)<kEps?0:d>0?1:-1;}
ifstream f("camera.in");
ofstream g("camera.out");
int n,i,j;
vector<Point> v,u;
Point Intersection(Point a,Point b,Point p,Point q)
{
double c1=det(a,b,p),c2=det(a,b,q);
assert(abs(c1-c2)>kEps); // undefined if parallel
return (c1*q-c2*p)/(c1-c2);
}
vector<Point> PolygonCut(const vector<Point>& P, Point s, Point e)
{
if(P.empty())return P;
vector<Point> res;int side1,side2;
side2=sgn(det(s,e,P.back()));
for(int i=0;i<(int)P.size();++i)
{
Point cur=P[i],prev=i?P[i-1]:P.back();
side1=sgn(det(s,e,cur));
if(side1*side2==-1)
res.push_back(Intersection(s,e,cur,prev));
if(side1>=0)res.push_back(cur);
side2=side1;
}
return res;
}
double Area(vector<Point> P)
{
int n=P.size();long double ans=0;
for(int i=0,j=n-1;i<n;j=i++)
ans+=(long double)cross(P[j],P[i]);
return abs(ans*.5);
}
int main()
{
f>>n;
int topp=0;
for(i=1;i<=n;i++)
{
double x,y;
f>>x>>y;
v.emplace_back(x,y);
u.emplace_back(x,y);
if(v[topp].imag()<v.back().imag())
topp=i-1;
}
if(Area(v)<-kEps)reverse(u.begin(),u.end());
// for(auto it:v)
// g<<real(it)<<' '<<imag(it)<<'\n';
for(j=n-1,i=0;i<n;j=i++)
v=PolygonCut(v,u[j],u[i]);
g<<fixed<<setprecision(2)<<Area(v);
return 0;
}