Pagini recente » Cod sursa (job #186282) | Cod sursa (job #1826393) | Cod sursa (job #1108916) | Cod sursa (job #2032270) | Cod sursa (job #784315)
Cod sursa(job #784315)
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
#define x first
#define y second
const int Nmax = 10010;
const int oo = 100010;
#define EPS 0.000001
ifstream F("camera.in");
ofstream G("camera.out");
typedef pair<double,double> Pair;
Pair A[Nmax],B[Nmax],C[Nmax];
double Sol;
int Semn,N,M,P;
double Aria(Pair A[],int N)
{
double Sum=0;
for (int i=1;i<=N;++i)
Sum+=A[i].x*A[i+1].y-A[i+1].x*A[i].y;
return Sum/2;
}
int Sign(Pair A, Pair B, Pair C)
{
double a = A.y - B.y;
double b = B.x - A.x;
double c = - B.x * A.y + B.y * A.x;
if ( a*C.x+b*C.y+c > -EPS ) return 1;
if ( a*C.x+b*C.y+c < EPS ) return -1;
return 0;
}
Pair Int(Pair A,Pair B,Pair A2,Pair B2)
{
double a1 = A.y - B.y ;
double b1 = B.x - A.x ;
double c1 = - A.y * B.x + B.y * A.x ;
double a2 = A2.y - B2.y ;
double b2 = B2.x - A2.x ;
double c2 = - A2.y * B2.x + B2.y * A2.x ;
double d = a1*b2-a2*b1;
if ( fabs(d)<EPS )
return make_pair(-2*oo,-2*oo);
return make_pair( (a2*c1-b1*c2)/d,(a1*c2-a2*c1)/d );
}
int main()
{
F>>N;
for (int i=1;i<=N;++i)
F>>A[i].x>>A[i].y;
A[N+1]=A[1];
Semn=( Aria(A,N)>0 ) ? +1 : -1;
M=4;
B[1]=make_pair(-oo,+oo);
B[2]=make_pair(+oo,+oo);
B[3]=make_pair(+oo,-oo);
B[4]=make_pair(-oo,-oo);
B[5]=make_pair(-oo,+oo);
for (int i=1;i<=N;++i)
{
int Act,Next;
P=0;
if ( M<3 )
{
G<<0<<'\n';
return 0;
}
for (Act=1;Act<=M;++Act)
{
Next=Act+1;
int S1 = Sign(A[i],A[i+1],B[Act]);
int S2 = Sign(A[i],A[i+1],B[Next]);
if (S1 != Semn && S2 != Semn)
C[++P] = B[Next];
if (S1 != Semn && S2 == Semn)
C[++P] = Int(A[i], A[i+1], B[Act], B[Next]);
if (S1 == Semn && S2 != Semn)
C[++P] = Int(A[i], A[i+1], B[Act], B[Next]),
C[++P] = B[Next];
if ( P>1 )
if ( C[P-1].x == -2*oo || C[P-1].y == -2*oo ) swap(C[P-1],C[P]),--P;
if ( P>0 )
if ( C[P].x == -2*oo || C[P].y == -2*oo ) --P;
}
M=P;
for (int i=1;i<=M;++i) B[i]=C[i];
}
Sol = Aria(B,M) ;
G<< fixed << setprecision(2) << Sol<<'\n';
}