Pagini recente » Borderou de evaluare (job #1103188) | Cod sursa (job #621647) | Borderou de evaluare (job #536494) | Cod sursa (job #1736225) | Cod sursa (job #1722129)
#include<cstdio>
#define MAXN 2010
#define INF 100000.0
#define EPS 1e-6
using namespace std;
struct Point{
double x;
double y;
};
Point v[MAXN],solution[MAXN],newSolution[MAXN];
int n,orientation,vertices=4;
double Determinant(Point a,Point b,Point c){
return a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y;
}
int Sign(double x){
if(x>EPS)
return 1;
if(x<-EPS)
return -1;
return 0;
}
Point Intersection(Point a,Point b,Point c,Point d){
double a1,b1,c1,a2,b2,c2;
Point answer;
a1=b.y-a.y;
b1=a.x-b.x;
c1=b.x*a.y-b.y*a.x;
a2=d.y-c.y;
b2=c.x-d.x;
c2=d.x*c.y-d.y*c.x;
if(Sign(a1*b2-a2*b1)==0){
answer.x=c2*b1-c1*b2;
answer.y=a1*c2-a2*c1;
}
else{
answer.x=(c2*b1-c1*b2)/(a1*b2-a2*b1);
answer.y=(a1*c2-a2*c1)/(a2*b1-a1*b2);
}
return answer;
}
void CutPolygon(Point a,Point b){
int i,newVertices=0,firstSign,secondSign;
for(i=1;i<=vertices;i++){
firstSign=Sign(Determinant(a,b,solution[i]));
secondSign=Sign(Determinant(a,b,solution[i+1]));
if(firstSign==orientation&&secondSign==orientation){
newVertices++;
newSolution[newVertices]=solution[i+1];
}
if(firstSign==orientation&&secondSign!=orientation){
newVertices++;
newSolution[newVertices]=Intersection(a,b,solution[i],solution[i+1]);
}
if(firstSign!=orientation&&secondSign==orientation){
newVertices++;
newSolution[newVertices]=Intersection(a,b,solution[i],solution[i+1]);
newVertices++;
newSolution[newVertices]=solution[i+1];
}
}
vertices=newVertices;
for(i=1;i<=vertices;i++)
solution[i]=newSolution[i];
solution[vertices+1]=solution[1];
}
int main(){
freopen("camera.in","r",stdin);
freopen("camera.out","w",stdout);
int i;
double area=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
v[n+1]=v[1];
for(i=1;i<=n;i++)
area+=Determinant({0,0},v[i],v[i+1]);
if(area>0)
orientation=1;
else
orientation=-1;
solution[1].x=solution[1].y=-INF;
solution[2].x=INF;
solution[2].y=-INF;
solution[3].x=solution[3].y=INF;
solution[4].x=-INF;
solution[4].y=INF;
solution[5]=solution[1];
for(i=1;i<=n;i++)
CutPolygon(v[i],v[i+1]);
area=0;
for(i=1;i<=vertices;i++)
area+=Determinant({0,0},solution[i],solution[i+1]);
if(area<0)
area=-area;
area/=2.0;
printf("%.2f",area);
return 0;
}