Pagini recente » Cod sursa (job #193480) | Cod sursa (job #2358714) | Cod sursa (job #1297894) | Cod sursa (job #672452) | Cod sursa (job #781768)
Cod sursa(job #781768)
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#define x first
#define y second
#define NM 2010
#define INF 1e6
using namespace std;
ifstream f("camera.in");
ofstream g("camera.out");
typedef pair<double, double> PD;
const double EPS=0.000001;
PD V[NM];
int N,i,j,Sign[NM],M,a,b,c;
vector<PD> PLG,PLX;
double ANS;
int FindSign (const PD& P1, const PD& P2, const PD& P3)
{
double S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
if (S>EPS) return 1;
if (S<-EPS) return -1;
return 0;
}
void Intersect (const PD& P, const PD& Q, const PD& R, const PD& S)
{
double A1,B1,C1,A2,B2,C2,D;
A1=1.0*Q.y-P.y;
B1=P.x-Q.x;
C1=A1*P.x+B1*P.y;
A2=1.0*S.y-R.y;
B2=R.x-S.x;
C2=A2*R.x+B2*R.y;
D=A1*B2-A2*B1;
if (fabs(D)<EPS)
{
PLX.push_back(make_pair(-INF,-INF));
return;
}
PLX.push_back(make_pair((B2*C1-B1*C2)/D,(A1*C2-A2*C1)/D));
return;
}
double Solve (int Sg)
{
PLG.clear();
PLG.push_back(make_pair(-INF,-INF));
PLG.push_back(make_pair(-INF,INF));
PLG.push_back(make_pair(INF,INF));
PLG.push_back(make_pair(INF,-INF));
for (i=1; i<=N; i++)
{
PLX.clear();
M=PLG.size();
for (j=0; j<M; j++)
Sign[j]=FindSign(V[i],V[i+1],PLG[j]);
for (j=0; j<M; j++)
{
a=j;
b=j+1;
if (b>=M) b-=M;
if (Sign[a]*Sg<=0 && Sign[b]*Sg<=0)
{
PLX.push_back(PLG[b]);
}
if (Sign[a]*Sg<=0 && Sign[b]*Sg>0)
{
Intersect(V[i],V[i+1],PLG[a],PLG[b]);
}
if (Sign[a]*Sg>0 && Sign[b]*Sg>0) continue;
if (Sign[a]*Sg>0 && Sign[b]*Sg<=0)
{
Intersect(V[i],V[i+1],PLG[a],PLG[b]);
PLX.push_back(PLG[b]);
}
}
PLG=PLX;
}
double ANS=0;
M=PLG.size();
for (i=0; i<M; i++)
{
a=i-1;
if (a<0) a+=M;
b=i;
c=i+1;
if (c>=M) c-=M;
ANS+=PLG[b].x*PLG[c].y-PLG[b].x*PLG[a].y;
}
ANS=max(ANS,-ANS);
return ANS/2.0;
}
int main ()
{
f >> N;
for (i=1; i<=N; i++)
f >> V[i].x >> V[i].y;
V[N+1]=V[1];
ANS=Solve(1);
if (fabs(ANS)<EPS) ANS=Solve(-1);
g << fixed << setprecision(2) << ANS << '\n';
f.close();
g.close();
return 0;
}