Pagini recente » Cod sursa (job #853260) | Cod sursa (job #2415530) | Cod sursa (job #3240145) | Cod sursa (job #2327543) | Cod sursa (job #1226839)
#include<fstream>
#include<iomanip>
#include<algorithm>
#define N 2010
#define punct pair<double,double>
#define eps 1e-6
#define x first
#define y second
#define INF 100002
#define mp make_pair
#define abs1(x) max(x, -x)
using namespace std;
ifstream f("camera.in");
ofstream g("camera.out");
int i,n,m,j,p1,p2,mn,semn[N];
double a,b,c;
punct p[N],sol[N],soln[N];
inline double Aria_poligonului(punct a[N],int n){
double s = 0;
a[n + 1] = a[1];
for(i = 1; i <= n; ++i)
s += a[i].x * a[i + 1].y - a[i].y * a[i + 1].x;
return s / 2;
}
inline punct punct_intersectie(punct p1 , punct p2){
double a1 , b1 , c1;
a1 = p2.y - p1.y;
b1 = p1.x - p2.x;
c1 = p2.x * p1.y - p2.y * p1.x;
double det = a * b1 - a1 * b;
return (punct){(b * c1 - b1 * c) / det , (a1 * c - c1 * a) /det };
}
inline bool poz_punct(punct p){
double det = a * p.x + b * p.y + c;
if(det <= eps)
return 1;
return 0;
}
int main()
{
f >> n;
for(i = 1; i <= n; ++i)
f >> p[i].x >> p[i].y;
p[n + 1] = p[1];
if(Aria_poligonului(p, n) < -eps)
reverse(p + 1, p + n + 1);
p[n + 1] = p[1];
sol[1] = mp(-INF, -INF);
sol[2] = mp(INF, -INF);
sol[3] = mp(INF, INF);
sol[4] = mp(-INF, INF);
m = 4;
for(i = 1; i <= n; ++i)
{
a = p[i + 1].y - p[i].y;
b = p[i].x - p[i + 1].x;
c = p[i + 1].x * p[i].y - p[i].x * p[i + 1].y;
sol[m + 1] = sol[1];
for(j = 1; j <= m + 1; ++j)
semn[j] = poz_punct(sol[j]);
mn = 0;
for(j = 1; j <= m; ++j)
{
p1 = semn[j];
p2 = semn[j + 1];
if(p1 && p2)
soln[++mn] = sol[j + 1];
else
if(p1 && !p2)
soln[++mn] = punct_intersectie(sol[j], sol[j + 1]);
else
if(!p1 && p2)
soln[++mn] = punct_intersectie(sol[j], sol[j + 1]),
soln[++mn] = sol[j + 1];
}
for(j = 1; j <= m; ++j)
sol[j] = soln[j];
m = mn;
}
g << fixed << setprecision(2) << abs1(Aria_poligonului(sol, m)) << '\n';
return 0;
}