Pagini recente » Cod sursa (job #2961502) | Cod sursa (job #803474) | Cod sursa (job #2655388) | Cod sursa (job #576849) | Cod sursa (job #117251)
Cod sursa(job #117251)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define inf 1000000
#define nmax 1505
#define pb push_back
using namespace std;
typedef pair<double, double> dd;
int n, T;
double ar;
dd pt[nmax];
vector <dd> rez, nr;
inline double absol(double x)
{
if(x < 0) return -x;
else return x;
}
void init()
{
rez.clear();
rez.pb(dd(-inf, -inf));
rez.pb(dd(-inf, inf));
rez.pb(dd(inf, inf));
rez.pb(dd(inf, -inf));
}
inline dd intersect(dd p1, dd p2, dd p3, dd p4)
{
double a1 = p2.second - p1.second;
double b1 = p1.first - p2.first;
double c1 = a1 * p1.first + b1 * p1.second;
double a2 = p4.second - p3.second;
double b2 = p3.first - p4.first;
double c2 = a2 * p3.first + b2 * p3.second;
double det = a1 * b2 - a2 * b1;
if(det == 0) return dd(inf, inf);
else return dd((double)(b2 * c1 - b1 * c2) / det, (double)(a1 * c2 - a2 * c1) / det);
}
inline double cp(dd p1, dd p2, dd p3)
{
double x1 = p2.first - p1.first;
double y1 = p2.second - p1.second;
double x2 = p3.first - p1.first;
double y2 = p3.second - p1.second;
return (double)x1 * y2 - x2 * y1;
}
void calc()
{
for(int i = 1; i <= n; i++)
{
nr.clear();
rez.pb(rez[0]);
for(int j = 0; j < (int)rez.size() - 1; j++)
{
if(cp(pt[i], pt[i + 1], rez[j]) > 0)
{
if(cp(pt[i], pt[i + 1], rez[j + 1]) < 0)
nr.pb(intersect(rez[j], rez[j + 1], pt[i], pt[i + 1]));
}
else
{
nr.pb(rez[j]);
if(cp(pt[i], pt[i + 1], rez[j + 1]) > 0)
nr.pb(intersect(rez[j], rez[j + 1], pt[i], pt[i + 1]));
}
}
rez = nr;
}
}
double arie(vector <dd> a)
{
double ar = 0;
for(int i = 1; i < (int)a.size() - 1; i++)
{
double x1 = a[i].first - a[0].first;
double y1 = a[i].second - a[0].second;
double x2 = a[i + 1].first - a[0].first;
double y2 = a[i + 1].second - a[0].second;
double cr = x1 * y2 - x2 * y1;
ar += cr;
}
return absol(ar / 2.0);
}
int main()
{
freopen("camera.in", "r", stdin);
freopen("camera.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lf%lf", &pt[i].first, &pt[i].second);
pt[n + 1] = pt[1];
init();
calc();
ar = arie(rez);
printf("%.2lf\n", ar);
return 0;
}