Pagini recente » Cod sursa (job #3180198) | Rating Vlad Victor (Paladinqaz) | Cod sursa (job #2150184) | Cod sursa (job #619499) | Cod sursa (job #2115518)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3;
const double EPS = 1e-6;
const double MAXCOORD = 1e5;
struct Point {
double x, y;
Point (double a, double b) : x(a), y(b) {}
};
struct Line {
double a, b, c;
Line (Point A, Point B) : a(B.y - A.y), b(A.x - B.x), c(A.y * B.x - A.x * B.y) {}
};
vector <Point> v, intrs;
inline int sgn(double value) {
if (fabs(value) < EPS)
return 0;
if (value > 0)
return 1;
return -1;
}
inline double det(Point A, Point B, Point C) {
return A.x * B.y + B.x * C.y + C.x * A.y - A.x * C.y - B.x * A.y - C.x * B.y;
}
inline double area(vector <Point> &polygon) {
if (polygon.size() < 3U)
return 0.0;
double ans = det(polygon.back(), polygon.front(), {0, 0});
for (int i = 1; i < (int) polygon.size(); ++i)
ans += det(polygon[i - 1], polygon[i], {0, 0});
return ans;
}
inline Point inters(Line d1, Line d2) {
double x = (d1.b * d2.c - d1.c * d2.b) / (d1.a * d2.b - d1.b * d2.a);
double y = (d1.c * d2.a - d1.a * d2.c) / (d1.a * d2.b - d1.b * d2.a);
return {x, y};
}
void cut_from_polygon(Point P1, Point P2) {
vector <Point> new_intrs;
Line d(P1, P2);
intrs.push_back(intrs[0]);
for (int i = 1; i < (int) intrs.size(); ++i) {
int sgn1 = sgn(det(P1, P2, intrs[i - 1])), sgn2 = sgn(det(P1, P2, intrs[i]));
Point P = inters(d, Line(intrs[i - 1], intrs[i]));
if (sgn1 * sgn2 == -1)
new_intrs.push_back(P);
if (sgn2 >= 0)
new_intrs.push_back(intrs[i]);
}
intrs = new_intrs;
}
int main()
{
int n;
ifstream fin("camera.in");
fin >> n;
for (int i = 0; i < n; ++i) {
double a, b;
fin >> a >> b;
v.push_back({a, b});
}
fin.close();
v.push_back(v[0]);
if (area(v) < 0)
reverse(v.begin(), v.end());
intrs.push_back({MAXCOORD, MAXCOORD});
intrs.push_back({-MAXCOORD, MAXCOORD});
intrs.push_back({-MAXCOORD, -MAXCOORD});
intrs.push_back({MAXCOORD, -MAXCOORD});
for (int i = 1; i < (int) v.size() && intrs.size() > 2U; ++i)
cut_from_polygon(v[i - 1], v[i]);
ofstream fout("camera.out");
fout << setprecision(2) << fixed << fabs(area(intrs)) / 2.0;
fout.close();
return 0;
}