Pagini recente » Cod sursa (job #2436226) | Cod sursa (job #529168) | Cod sursa (job #2445734) | Cod sursa (job #2952500) | Cod sursa (job #1182474)
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#define INF 100001
#define eps 1e-6
#define N 2010
using namespace std;
ifstream f("camera.in");
ofstream g("camera.out");
int i,j,n,m,nm,parte[N];
double a,b,c;
struct punct {double x,y;}sol[N],p[N],ns[N];
inline double aria(){
double s = 0;
p[n + 1] = p[1];
for(i = 1 ; i <= n ; ++ i)
s += p[i].x * p[i + 1].y - p[i].y * p [i + 1].x;
return s;
}
inline int afla_parte(double x,double y){
double p = x * a + y * b + c;
if(p < -eps)
return -1;
else
if(p > eps)
return 1;
return 0;
}
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 double my_abs(double x)
{
if(x < 0)
return -x;
return x;
}
int main()
{
f >> n;
for(i = 1 ; i <= n ; ++ i)
{
f >> p[i].x >> p[i].y;
}
sol[1] = (punct){INF , INF};
sol[2] = (punct){-INF, INF};
sol[3] = (punct){-INF,-INF};
sol[4] = (punct){INF ,-INF};
m = 4;
if(aria() > eps)
{
reverse(p + 1 , p + n + 1);
}
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;
for(j = 1 ; j <= m ; ++ j)
parte[j] = afla_parte(sol[j].x , sol[j].y);
nm = 0;
parte[m + 1] = parte[1];
sol[m + 1] = sol[1];
for(j = 1 ; j <= m ; ++ j)
{
if(parte[j] >= 0 && parte[j + 1] >= 0)
ns[++ nm] = sol[j];
else
if(parte[j] >= 0 && parte[j + 1] < 0)
ns[++ nm] = sol[j] , ns[++ nm] = punct_intersectie(sol[j] , sol[j + 1]);
else
if(parte[j] < 0 && parte[j + 1] >= 0)
ns[++ nm] = punct_intersectie(sol[j] , sol[j + 1]);
}
for(j = 1 ; j <= nm ; ++ j)
sol[j] = ns[j];
m = nm;
}
n = 0;
for(i = 1 ; i <= m ; ++i)
if(sol[i].x != p[n].x || sol[i].y != p[n].y)
p[++ n] = sol[i];
g << fixed << setprecision(2) << my_abs(aria()/2) << '\n';
return 0;
}