Nu aveti permisiuni pentru a descarca fisierul grader_test22.ok
Cod sursa(job #2531009)
Utilizator | Data | 25 ianuarie 2020 15:59:46 | |
---|---|---|---|
Problema | Camera | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 2.47 kb |
#include <bits/stdc++.h>
#define x first
#define y second
#define point pair<double,double>
using namespace std;
ifstream f("camera.in");
ofstream g("camera.out");
int n;
double area;
double sumx,sumy;
vector<point> p,r,a;
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);
}
void Read()
{
int x,y;
f>>n;
for(int i=1;i<=n;++i)
{
f>>x>>y;
sumx += x;
sumy += y;
p.push_back(make_pair(x,y));
}
r = 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 Prepare()
{
p.push_back(p[0]);
p.push_back(p[1]);
}
void Solve()
{
for(int i = 5;i < p.size() - 1;++i)
{
a.clear();
r.push_back(r[0]);
for(int j = 0;j < r.size() - 1;++j)
{
point curr = r[j];
point next = r[j + 1];
if(cross_product(p[i],p[i + 1],curr) > 0)
{
if(cross_product(p[i],p[i + 1],next) > 0)
a.push_back(next);
else
a.push_back(intersection(p[i],p[i + 1],curr,next));
}
else
{
if(cross_product(p[i],p[i + 1],next) >= 0)
{
a.push_back(intersection(p[i],p[i + 1],curr,next));
a.push_back(next);
}
}
}
r.clear();
r.assign(a.begin(),a.end());
}
}
void calculate_area()
{
r.push_back(r[0]);
for(int i = 0;i < r.size() - 1;++i)
area += r[i].x * r[i + 1].y - r[i + 1].x * r[i].y;
if(area < 0)
area = -area;
area /= 2.0;
}
void Print()
{
g<<setprecision(2)<<fixed;
g<<area;
g.close();
}
int main()
{
Read();
if( n > 4)
{
Prepare();
Solve();
}
calculate_area();
Print();
return 0;
}