Cod sursa(job #164583)

Utilizator anoukAnca Dumitrache anouk Data 24 martie 2008 15:45:28
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.83 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
#define DIM 55
#define eps 0.0001
using namespace std;

struct Punct {
  float x, y;
};
struct Comp {
  bool operator () (Punct A, Punct B)
  {
    if (B.y - A.y > eps) return true;
    if (fabs(B.y - A.y) < eps && B.x - A.x > eps) return true;
    return false;
  }
};

Punct A[DIM], B[DIM];
vector<Punct> p, P;
int N, M, L, l, st[DIM], sel[DIM], vf;
float aa, bb, cc;

void Hill();
int Semn(Punct A, Punct B, Punct C);
void Coef(Punct A, Punct B);
int Intersec(Punct A, Punct B, Punct C, Punct D);

int main()
{
  FILE *fin = fopen("arie.in" , "r");
  FILE *fout = fopen("arie.out", "w");

  fscanf(fin, "%d", &M);
  for (int i = 1; i <= M; i++)
    fscanf(fin, "%f%f", &A[i].x, &A[i].y);
  fscanf(fin, "%d", &N);
  for (int i = 1; i <= N; i++)
    fscanf(fin, "%f%f", &B[i].x, &B[i].y);
	
  for (int i = 1; i <= N; i++)
  {
    int gasit = 0;
    for (int j = 1; j <= M && !gasit; j++)
      if (fabs(A[j].x - B[i].x) < eps && fabs(A[j].y - B[i].y) < eps) gasit = 1;
    if (gasit)
      p.push_back(B[i]);
  }
  A[M + 1] = A[1]; A[M + 2] = A[2];
  B[N + 1] = B[1]; B[N + 2] = B[2];
  for (int i = 1; i <= M; i++)
  {
    int interior = 1;
    for (int j = 1; j <= N && interior; j++)
    {
      Coef(B[j], B[j + 1]);
      if ( (aa * A[i].x + bb * A[i].y + cc) * (aa * B[j + 2].x + bb * B[j + 2].y + cc) <= eps) interior = 0;
    }
    if (interior)
    {
      p.push_back(A[i]);
      L++;
    }
  }
  for (int i = 1; i <= N; i++)
  {
    int interior = 1; 
    for (int j = 1; j <= M && interior; j++)
    {
      Coef(A[j], A[j + 1]);
      if ( (aa * B[i].x + bb * B[i].y + cc) * (aa * A[j + 2].x + bb * A[j + 2].y + cc) <= eps) interior = 0;
    }
    if (interior)
    {
      p.push_back(B[i]);
      L++;
    }
  }
  for (int i = 1; i <= M; i++)
    for (int j = 1; j <= N; j++)
      if (Intersec(A[i], A[i + 1], B[j], B[j + 1]))
  {
	// cout << A[i].x << " " << A[i].y << " " << A[i + 1].x << " " << A[i + 1].y << "  " << B[i].x << " " << B[i].y << " " << B[i + 1].x << " " << B[i + 1].y; cin.get();
    Coef(A[i], A[i + 1]); float a1 = aa, b1 = bb, c1 = cc;
    Coef(B[j], B[j + 1]); float a2 = aa, b2 = bb, c2 = cc;
    Punct X;
    X.x = - (b1 * c2 - c1 * b2) / (b1 * a2 - b2 * a1);
    X.y = - (a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1);
    p.push_back(X);
    L++;
  }
  sort(p.begin(), p.end(), Comp());
  Hill();
  for (int i = 1; i <= vf; i++)
    P.push_back(p[st[i] - 1]);
  float arie = 0.0;	
  for (int i = 0; i < P.size(); i++)
    arie += P[i].x * P[i + 1].y - P[i + 1].x * P[i].y;
  arie /= 2.0;
  arie = arie > eps ? arie : 0.000 ;
  fprintf(fout, "%.3f\n", fabs(arie));

  fclose(fin);
  fclose(fout);
  return 0;
}

void Hill()
{
  st[1] = 1; st[2] = 2;
  sel[2] = 1;
  vf = 2;
  int pas = 1, i = 2;
  while (i > 1)
  {
    while (sel[i])
    {
      if (pas == 1)
      {
        i++;
        if (i == L) pas = -1;
      }
      else i--;
    }
    if (i == 0) break;
    while (vf > 1 && Semn(p[st[vf - 1] - 1], p[st[vf] - 1], p[i - 1]) == -1)
    {
      sel[st[vf]] = 0;
      vf--;
    }
    vf++;
    sel[i] = 1;
    st[vf] = i;
  }
}

int Semn(Punct A, Punct B, Punct C)
{
  Coef(A, B);
  if (aa * C.x + bb * C.y + cc < -eps) return -1;
  return 1;
}

void Coef(Punct A, Punct B)
{
  aa = A.y - B.y;
  bb = B.x - A.x;
  cc = A.x * B.y - A.y * B.x;
}

int Intersec(Punct A, Punct B, Punct C, Punct D)
{
//	cout << A.x << " " << A.y << " " << B.x << " " << B.y << " " << C.x << " " << C.y << " " << D.x << " " << D.y; cin.get();
  Coef(A, B);
//	cout << aa*C.x + bb*C.y + cc << " " << aa*D.x + bb*D.y + cc; cin.get();
  if ((aa * C.x + bb * C.y + cc) * (aa * D.x + bb * D.y + cc) > 0.0) return 0;
  Coef(C, D);
//	cout << aa*A.x + bb * A.y + cc << " " << aa * B.x + bb * B.y + cc; cin.get();
  if ((aa * A.x + bb * A.y + cc) * (aa * B.x + bb * B.y + cc) > 0.0) return 0;
  return 1;
}