Pagini recente » Diferente pentru preoni-2007/runda-1/solutii intre reviziile 28 si 33 | Istoria paginii documentatie | Profil AsthenicDog390 | Heavy metal | Cod sursa (job #2531491)
#include <bits/stdc++.h>
#define x first
#define y second
#define point pair<double,double>
using namespace std;
ofstream g("camera.out");
int n;
long double area;
long double sumx,sumy;
vector<point> p,r,p1;
int poz = 31999;
char buffer[32010];
void inc()
{
++poz;
if(poz == 32000)
{
fread(buffer,1,32000,stdin);
poz = 0;
}
}
void read(int &x)
{
char sign = '+';
x = 0;
while(buffer[poz] < '0' || buffer[poz] > '9')
{
sign = buffer[poz];
inc();
}
while(buffer[poz] >= '0' && buffer[poz] <= '9')
{
x = x * 10 + buffer[poz] - '0';
inc();
}
if(sign == '-')
x = -x;
}
bool exist(point po1)
{
for(int i = 0;i <p1.size();++i)
if(p[i].x == po1.x && p[i].y == po1.y)
return true;
return false;
}
bool cmp(point po1,point po2)
{
return atan2(po1.x - sumx / n,po1.y - sumy / n) > atan2(po2.x - sumx / n,po2.y - sumy / n);
}
bool cmp1(point po1,point po2)
{
return atan2(po1.x - sumx / r.size(),po1.y - sumy / r.size()) > atan2(po2.x - sumx / r.size(),po2.y - sumy / r.size());
}
void Read()
{
freopen("camera.in","r",stdin);
int x,y;
read(n);
for(int i=1;i<=n;++i)
{
read(x);
read(y);
sumx += x;
sumy += y;
p.push_back(make_pair(x,y));
}
fclose(stdin);
sort(p.begin(),p.end(),cmp);
p.push_back(p[0]);
p1 = p;
}
point intersection(point po1,point po2,point po3,point po4)
{
double x1 = po1.y - po2.y;
double y1 = po2.x - po1.x;
double c1 = po1.x * po2.y - po2.x * po1.y;
double x2 = po3.y - po4.y;
double y2 = po4.x - po3.x;
double c2 = po3.x * po4.y - po4.x * po3.y;
double x = (y1 * c2 - y2 * c1) / (x1 * y2 - x2 * y1);
double y = (c2 * x1 - c1 * x2) / (y1 * x2 - y2 * x1);
return {x , y};
}
int cross_product(point po1,point po2,point po3)
{
return (po2.y - po3.y) * (po1.x - po3.x) - (po1.y - po3.y) * (po2.x - po3.x);
}
void intersection_points()
{
for(int i = 0;i < p.size() - 3;++i)
for(int j = i + 2;j < p.size();++j)
{
point result = intersection(p[i],p[i+1],p[j],p[j+1]);
if(!exist(result) && result.x <= 200000 && result.y <= 200000)
p1.push_back(result);
}
}
void Solve()
{
for(int i = 0;i < p.size() - 1;++i)
{
r.clear();
for(int j = 0;j < p1.size();++j)
{
point curr = p1[j];
if(cross_product(p[i],p[i + 1],curr) >= 0)
r.push_back(curr);
}
p1.clear();
p1 = r;
}
}
void calculate_area()
{
sumx = sumy = 0;
for(int i=0;i<r.size();++i)
{
sumx += r[i].x;
sumy += r[i].y;
}
r.push_back(r[0]);
for(int i = 0;i < r.size() - 1;++i)
area += r[i].x * r[i+1].y - r[i].y * r[i+1].x;
if(area < 0)
area = -area;
area /= 2.0;
}
void Print()
{
g<<setprecision(2)<<fixed;
g<<area;
g.close();
}
int main()
{
Read();
intersection_points();
Solve();
calculate_area();
Print();
return 0;
}