Pagini recente » Cod sursa (job #800682) | Cod sursa (job #1236344) | Cod sursa (job #2528132) | Cod sursa (job #1057521) | Cod sursa (job #1160551)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define NMAX 20001
#define INF 1000000
#define pb push_back
int N,sz[2];
struct punct
{double x , y;}P1[NMAX],P[NMAX] ,sol[2][4*NMAX];
float A;
double det(punct p1 , punct p2 ,punct p3)
{
return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p2.y*p3.x - p3.y*p1.x - p2.x*p1.y;
}
punct intersect(punct p1 ,punct p2 , punct p3 , punct p4 )
{
punct p;
double a1 , b1 , c1 , a2 , b2 , c2 ;
a1 = p2.y-p1.y; a2 = p4.y-p3.y;
b1 = p1.x-p2.x; b2 = p3.x-p4.x;
c1 = p1.y*p2.x-p1.x*p2.y; c2 = p3.y*p4.x-p3.x*p4.y;
p.x = (b1*c2-b2*c1)/(a1*b2-a2*b1);
p.y = (a1*c2-a2*c1)/(b1*a2-b2*a1);
return p;
}
int main()
{
freopen("camera.in" , "r" , stdin );
freopen("camera.out" , "w" , stdout );
scanf("%d" , &N );
for(int i = 1 ; i<= N ; ++i )
scanf("%lf%lf" , &P1[i].x , &P1[i].y );
P1[N+1] = P1[1];
for(int i = 1 ; i <= N ; ++i )
A+=det(P1[0],P1[i],P1[i+1]);
for(int i = 1 ; i <= N ; ++i )
if(A < 0)P[i] = P1[N-i+1];
else P[i] = P1[i];
P[N+1] = P[1];
punct p;
p.x = -INF,p.y = -INF;sol[0][1] = p;
p.x = INF;sol[0][2] = p;
p.y = INF;sol[0][3] = p;
p.x =-INF;sol[0][4] = p;
sol[0][5] = sol[0][1];
sz[0] = 4;
int l = 1 ;
for(int i = 1 ; i <= N ; ++i )
{
sz[l] = 0;
for(int j = 1 ; j <= sz[1-l] ; ++j )
{
punct p1 = sol[1-l][j] , p2 = sol[1-l][j+1];
float d1 = det(P[i],P[i+1],sol[1-l][j]) , d2 = det(P[i],P[i+1],sol[1-l][j+1]) ;
if(d1 < 0)
{
if(d2 < 0)continue;
sol[l][++sz[l]] = intersect(P[i],P[i+1],sol[1-l][j],sol[1-l][j+1]);
sol[l][++sz[l]] = sol[1-l][j+1];
}
else
{
if(d2 >= 0)sol[l][++sz[l]] = sol[1-l][j+1];
else sol[l][++sz[l]] = intersect(P[i],P[i+1],sol[1-l][j],sol[1-l][j+1]);
}
}
sol[l][sz[l]+1] = sol[l][1];
l = 1-l;
}
A = 0;
for(int i = 1 ; i<= sz[1-l] ; ++i )
A+=det(P[0],sol[1-l][i],sol[1-l][i+1]);
if(A < 0)A = -A;
A/=2;
printf("%.2f" , A);
return 0;
}