Pagini recente » Cod sursa (job #1286481) | Cod sursa (job #703779) | Cod sursa (job #1186514) | Cod sursa (job #1279108) | Cod sursa (job #1907460)
#include <fstream>
#include <algorithm>
#include <string.h>
#include <iomanip>
#define NMax 2010
#define INF 1000000
#define eps 0.00001
using namespace std;
ifstream f("camera.in");
ofstream g("camera.out");
struct Point {
double x;
double y;
Point() {};
Point(double _x, double _y) {
x = _x;
y = _y;
}
bool operator==(Point p1) {
if (this->x == p1.x && this->y == p1.y)
return true;
return false;
}
} polyg[NMax], crt[NMax], nex[NMax];
int n, nP, newNP;
double mabs(double d1)
{
if (d1 < 0)
return -d1;
return d1;
}
double det(Point p1, Point p2, Point p3)
{
return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p3.x*p2.y - p1.x*p3.y - p2.x*p1.y;
}
double tri_area(Point p1, Point p2)
{
return p1.x*p2.y - p2.x*p1.y;
}
Point get_intersection_coords(Point p1, Point p2, Point p3, Point p4)
{
double a1 = p2.y - p1.y;
double b1 = p1.x - p2.x;
double c1 = p1.y*p2.x - p1.x*p2.y;
double a2 = p4.y - p3.y;
double b2 = p3.x - p4.x;
double c2 = p3.y*p4.x - p3.x*p4.y;
Point answ;
answ.x = (b1*c2 - b2*c1) / (a1*b2 - a2*b1);
answ.y = (a2*c1 - a1*c2) / (a1*b2 - a2*b1);
return answ;
}
double dist(Point p1, Point p2)
{
return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
int sign(double d1)
{
if (d1 > -eps && d1 < eps)
return 0;
else if (d1 > eps)
return 1;
else
return -1;
}
int main()
{
f >> n;
Point leftCorner(INF, INF), rightCorner(0, 0), lowest;
for (int i = 1; i <= n; i++) {
f >> polyg[i].x >> polyg[i].y;
if (leftCorner.x > polyg[i].x)
leftCorner.x = polyg[i].x;
if (leftCorner.y > polyg[i].y)
leftCorner.y = polyg[i].y;
if (rightCorner.x < polyg[i].x)
rightCorner.x = polyg[i].x;
if (rightCorner.y < polyg[i].y)
rightCorner.y = polyg[i].y;
}
crt[++nP] = Point(leftCorner.x, leftCorner.y);
crt[++nP] = Point(rightCorner.x, leftCorner.y);
crt[++nP] = Point(rightCorner.x, rightCorner.y);
crt[++nP] = Point(leftCorner.x, rightCorner.y);
crt[nP + 1] = crt[1];
polyg[n + 1] = polyg[1];
double area = 0;
for (int i = 1; i <= n; i++)
area += tri_area(polyg[i], polyg[i + 1]);
if (area < 0)
for (int i = 1; i <= n / 2; i++)
swap(polyg[i], polyg[n - i + 1]);
polyg[n + 1] = polyg[n];
for (int i = 1; i <= n; i++) {
Point p1 = polyg[i];
Point p2 = polyg[i + 1];
for (int j = 1; j <= nP; j++) {
Point p3 = crt[j];
Point p4 = crt[j + 1];
if (sign(det(p1, p2, p3)) * sign(det(p1, p2, p4)) < 0) {
Point intersection = get_intersection_coords(p1, p2, p3, p4);
if (sign( det(p1, p2, p4)) > 0) {
nex[++newNP] = intersection;
nex[++newNP] = p4;
}
else
nex[++newNP] = intersection;
}
else
if (sign(det(p1, p2, p4)) >= 0)
nex[++newNP] = p4;
}
nP = newNP;
newNP = 0;
swap(crt, nex);
crt[nP + 1] = crt[1];
memset(nex, 0, sizeof(nex));
}
double answArea = 0;
for (int i = 1; i <= nP; i++)
answArea += tri_area(crt[i], crt[i + 1]);
g << setprecision(2) << fixed << 1.0 * mabs(answArea) / 2 << '\n';
return 0;
}