Pagini recente » Planificare infoarena | Sedinta 2008-10-10 | Sedinta 2009-01-26 | Planificare infoarena | Cod sursa (job #3210145)
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream cin("camera.in");
ofstream cout("camera.out");
int n;
vector<double> X;
vector<double> Y;
double arie;
const int M=100000;
int eps=1e-6;
vector<pair<double,double>> poligon;
double det(int a,int b,pair<double,double> p)
{
return X[a]*Y[b]+X[b]*p.second+Y[a]*p.first-Y[b]*p.first-p.second*X[a]-X[b]*Y[a];
}
int semn(double a)
{
if(-eps<a && a<eps)
return 0;
if(a>eps)
return 1;
return -1;
}
pair<double,double> intersectie (int a,int b,pair<double,double> c,pair<double,double> d)
{
double a1=Y[a]-Y[b];
double b1=X[b]-X[a];
double c1=X[a]*Y[b]-Y[a]*X[b];
double a2=c.second-d.second;
double b2=d.first-c.first;
double c2=c.first*d.second-c.second*d.first;
double new_y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
double new_x=(-c1-b1*new_y)/a1;
return {new_x,new_y};
}
void determinare(int a,int b)
{
vector<pair<double,double>> aux;
poligon.push_back(poligon[0]);
for(int i=0;i<poligon.size()-1;i++)
{
int semn1=semn(det(a,b,poligon[i]));
int semn2=semn(det(a,b,poligon[i+1]));
if(semn1*semn2==-1)
aux.push_back(intersectie(a,b,poligon[i],poligon[i+1]));
if(semn2>=0)
aux.push_back(poligon[i+1]);
}
poligon=aux;
}
int main()
{
cout<<setprecision(2)<<fixed;
cin>>n;
X.resize(n);
Y.resize(n);
for(int i=0;i<n;i++)
cin>>X[i]>>Y[i];
for(int i=0;i<n-1;i++)
arie=arie+X[i]*Y[i+1]-Y[i]*X[i+1];
arie=arie+X[n-1]*Y[0]-Y[n-1]*X[0];
if(arie<0)
{
reverse(X.begin(),X.end());
reverse(Y.begin(),Y.end());
}
arie=abs(arie)/2;
poligon.push_back({-M,-M});
poligon.push_back({M,-M});
poligon.push_back({M,M});
poligon.push_back({-M,M});
for(int i=0;i<n-1;i++)
determinare(i,i+1);
determinare(n-1,0);
if(poligon.size()==0)
cout<<0;
else
{
arie=0;
for(int i=0;i<poligon.size()-1;i++)
arie=arie+poligon[i].first*poligon[i+1].second-poligon[i].second*poligon[i+1].first;
arie=arie+poligon[poligon.size()-1].first*poligon[0].second-poligon[poligon.size()-1].second*poligon[0].first;
arie=abs(arie)/2;
cout<<arie;
}
return 0;
}