Cod sursa(job #1755374)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 10 septembrie 2016 00:11:07
Problema Camera Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <cstdio>
#define MAXC 1000000
#define EPS 0.0000001
#define MAXN 2000
struct mycreation{
    double x, y;
}aux[MAXN+10], p[MAXN+10];
int x[MAXN], y[MAXN], k;
long long a;
bool ok[MAXN+10];
inline bool zero(double x){
    return ((x>-EPS)&&(x<EPS));
}
inline double arie(double x, double y, double a, double b, double p, double q){
    return x*b-y*a+a*q-b*p+p*y-q*x;
}
inline mycreation intersection(double x, double y, double a, double b, mycreation p, mycreation q){
    mycreation kterink;
    double smecherie=(x-a)*(p.y-q.y)-(y-b)*(p.x-q.x);
    if(zero(smecherie)) smecherie=1;
    kterink.x=((x*b-y*a)*(p.x-q.x)-(x-a)*(p.x*q.y-p.y*q.x))/smecherie;
    kterink.y=((x*b-y*a)*(p.y-q.y)-(y-b)*(p.x*q.y-p.y*q.x))/smecherie;
    return kterink;
}
inline bool nasol(double x){
    if(zero(x)) return 0;
    return ((x<0)!=(a<0));
}
inline void intersect(int x, int y, int a, int b){
    if(k==0) return ;
    int s, i, t;
    for(i=0; i<k; i++) if(nasol(arie(x, y, a, b, p[i].x, p[i].y))) ok[i]=1;
    s=0;
    for(i=0; i<k; i++) s+=ok[i];
    if(s==k){
        k=0;
        return ;
    }
    s=0;
    for(i=0; i<k; i++) if((ok[i])&&((i==0)||(ok[i-1]==0))) s++;
    if(s==2){
        t=0;
        i=0;
        while(ok[i]) i++;
        aux[t++]=intersection(x, y, a, b, p[i], p[i-1]);
        while(ok[i]==0){
            aux[t++]=p[i];
            i++;
        }
        aux[t++]=intersection(x, y, a, b, p[i], p[i-1]);
    }else if(s==1){
        t=0;
        i=0;
        while(ok[i]==0){
            aux[t++]=p[i];
            i++;
        }
        if(i==0) aux[t++]=intersection(x, y, a, b, p[k-1], p[i]);
        else aux[t++]=intersection(x, y, a, b, p[i-1], p[i]);
        while((i<k)&&(ok[i]==1)) i++;
        if(i==k) aux[t++]=intersection(x, y, a, b, p[k-1], p[0]);
        else aux[t++]=intersection(x, y, a, b, p[i-1], p[i]);
        while(i<k){
            aux[t++]=p[i];
            i++;
        }
    }
    k=t;
    for(i=0; i<k; i++) p[i]=aux[i], ok[i]=0;
}
int main(){
    int n, i;
    double b;
    FILE *fin, *fout;
    fin=fopen("camera.in", "r");
    fout=fopen("camera.out", "w");
    fscanf(fin, "%d", &n);
    for(i=0; i<n; i++) fscanf(fin, "%d%d", &x[i], &y[i]);
    a=1LL*x[n-1]*y[0]-1LL*x[0]*y[n-1];
    for(i=0; i<n; i++) a+=1LL*x[i]*y[i+1]-1LL*x[i+1]*y[i];
    p[0].x=p[0].y=p[1].x=p[3].y=MAXC;
    p[2].x=p[2].y=p[1].y=p[3].x=-MAXC;
    k=4;
    for(i=0; i<n; i++) intersect(x[i], y[i], x[(i+1)%n], y[(i+1)%n]);
    if(k==0) fprintf(fout, "0.00\n");
    else{
        b=p[k-1].x*p[0].y-p[0].x*p[k-1].y;
        for(i=0; i<k-1; i++) b+=p[i].x*p[i+1].y-p[i+1].x*p[i].y;
        if(b<0) b=-b;
        fprintf(fout, "%.2lf\n", b*0.5);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}