Pagini recente » Borderou de evaluare (job #1488892) | Cod sursa (job #2355374) | Cod sursa (job #383560) | Cod sursa (job #2104435) | Cod sursa (job #2339914)
#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;
void check(int poz)
{
Point nxt,prv;
nxt=(poz==n-1)?nxt=v[0]:nxt=v[poz+1];
prv=(!poz)?prv=v.back():prv=v[poz-1];
if(sgn(det(prv,v[poz],nxt))==-1)
reverse(u.begin(),u.end());
}
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;
}
check(topp);
// 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;
}