Cod sursa(job #1993571)

Utilizator MotoAMotoi Alexandru MotoA Data 23 iunie 2017 12:00:01
Problema Aria Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.42 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("arie.in");
ofstream g("are.out");
const double eps=1e-7;
struct Punct{
double x,y;
};
Punct p1[21],p2[21],p[43];
int M,N,K;

bool compx(Punct a,Punct b){
 if(a.x==b.x)return a.y<b.y;
 return a.x<b.x;
}
void citire(){
 f>>N;
 for(int i=1;i<=N;i++)
 f>>p1[i].x>>p1[i].y;
 p1[N+1]=p1[1];
 f>>M;
 for(int i=1;i<=M;i++)
 f>>p2[i].x>>p2[i].y;
 p2[M+1]=p2[1];
}
double det(Punct A, Punct B, Punct C)
{
    return (A.x - B.x) * (B.y - C.y) - (A.y - B.y) * (B.x - C.x);
}
bool compd(Punct a,Punct b){
 return det(p[1],a,b)<0;
}
bool interior(Punct p,Punct pol[],int n){
 double d1=det(p,pol[n],pol[1]);
 for(int i=1;i<n;i++){
  double d2=det(p,pol[i],pol[i+1]);
   if(d1*d2<=0)return 0;
 }
 return 1;
}

struct dreapta
{
    double a, b, c;
};
struct capat
{
    Punct U;
    int id;
};
int inters_dr(const dreapta &d1, const dreapta &d2, Punct &P)
{
    double Dd = d1.a * d2.b - d2.a * d1.b;
    double Dx = d1.b * d2.c - d2.b * d1.c;
    double Dy = d2.a * d1.c - d1.a * d2.c;
    if(abs(Dd) <= eps) //if(Dd == 0)
    {
        if(abs(Dx) <= eps) //if(Dx == 0)
            return 0;
        else
            return -1;
    }
    else
    {
        P.x = Dx / Dd;
        P.y = Dy / Dd;
        return 1;
    }
}
dreapta ec_dr(Punct A, Punct B)
{
    dreapta d;
    d.a = A.y - B.y;
    d.b = B.x - A.x;
    d.c = A.x * B.y - B.x * A.y;
    return d;
}
int pct_pe_seg(Punct M, Punct A, Punct B)
{
    double dx1 = M.x - A.x;
    double dx2 = M.x - B.x;
    double dy1 = M.y - A.y;
    double dy2 = M.y - B.y;
    // if(dx1 * dy2 == dx2 * dy1)
    if(dx1 * dx2 <= 0 && dy1 * dy2 <= 0) // au acelasi semn?
        return 1;
    else return 0;
}
bool compxy(capat A, capat B)
{
    if(A.U.x == B.U.x)
    {
        if(A.U.y == B.U.y)
        {
            return 0;
        }
        return A.U.y < B.U.y;
    }
    return A.U.x < B.U.x;
}
int int_seg(Punct A, Punct B, Punct C, Punct D, Punct &P1, Punct &P2)
{
    dreapta d1 = ec_dr(A, B);
    dreapta d2 = ec_dr(C, D);
    int k = inters_dr(d1, d2, P1);
    if(k == -1)return 0;
    if(k == 1)
    {
        if(pct_pe_seg(P1, A, B) && pct_pe_seg(P1, C, D))
            return 1;
        else
            return 0;
    }
    capat v[4] = {{A, 0}, {B, 0}, {C, 1}, {D, 1}};
    sort(v, v + 4, compxy);
    if(compxy(v[1], v[2]) == 0)
    {
        P1 = v[1].U;
        return 1;
    }
    if(v[0].id != v[1].id)
    {
        P1 = v[1].U;
        P2 = v[2].U;
        return 2;
    }
    return 0;
}
void inter(Punct p1[],int n,Punct p2[],int m){
 //int prec=interior(p1[n],p2,m);
 for(int i=1;i<=n;i++){
  int in=interior(p1[i],p2,m);
  if(in==1)p[++K]=p1[i];
 /*
  if(in!=prec){


  }
   prec=in;
 }*/
}
}
void inters(Punct p1[],int n,Punct p2[],int m){
  Punct P1,P2;
 for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++){
  switch(int_seg(p1[i],p1[i+1],p2[j],p2[j+1], P1, P2))
    {
    case 1:
        p[++K]=P1;
        break;
    case 2:
        p[++K]=P1;p[++K]=P2;
        break;
    }
  }
}

int main(){
citire();
inter(p1,N,p2,M);
inter(p2,M,p1,N);
inters(p2,M,p1,N);
int r=1;
for(int i=2;i<=K;i++)
 if(compx(p[i],p[r]))r=i;
 swap(p[1],p[r]);
 sort(p+2,p+K+1,compd);
 p[K+1]=p[1];
 double Arie=0;
 for(int i=1;i<=K;i++)
  Arie+=p[i].x*p[i+1].y-p[i+1].x*p[i].y;
  Arie/=2;
  g<<fixed<<setprecision(5)<<-Arie;
  return 0;
}