Cod sursa(job #1722128)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 27 iunie 2016 13:48:43
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#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;
}