Pagini recente » Cod sursa (job #2627232) | Cod sursa (job #2824957) | Cod sursa (job #1966537) | Cod sursa (job #1122455) | Cod sursa (job #2956236)
#include <bits/stdc++.h>
using namespace std;
#define int64 long long
#define MAX_N 250
struct Point { int x, y; };
int noPoints;
Point points[MAX_N];
vector<Point> points1, points2;
vector<Point> hull;
inline int64 orientation(const Point& a, const Point& b, const Point& c) {
return ((int64)b.y - a.y) * (c.x - b.x) - ((int64)b.x - a.x) * (c.y - b.y);
}
inline bool cmpPoints1(const Point& a, const Point& b) {
return orientation(points1[0], a, b) < 0;
}
inline bool cmpPoints2(const Point& a, const Point& b) {
return orientation(points2[0], a, b) < 0;
}
void splitPoints(const Point& a, const Point& b) {
int i;
points1.clear(), points2.clear();
for (i = 0; i < noPoints; ++i)
if (orientation(a, b, points[i]) < 0)
points1.push_back(points[i]);
else
points2.push_back(points[i]);
}
void setStartPoint(vector<Point>& points) {
unsigned int i;
for (i = 1; i < points.size(); ++i)
if (points[i].y < points[0].y ||
(points[i].y == points[0].y && points[i].x < points[0].x))
swap(points[0], points[i]);
}
void computeHull(vector<Point>& points) {
unsigned int i;
hull.clear();
hull.push_back(points[0]);
hull.push_back(points[1]);
for (i = 2; i < points.size(); ++i) {
while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull.back(), points[i]) >= 0)
hull.pop_back();
hull.push_back(points[i]);
}
}
bool checkSplit() {
if (points1.size() < 3 || points2.size() < 3)
return false;
setStartPoint(points1);
sort(points1.begin(), points1.end(), cmpPoints1);
computeHull(points1);
if (hull.size() != points1.size()) return false;
setStartPoint(points2);
sort(points2.begin(), points2.end(), cmpPoints2);
computeHull(points2);
if (hull.size() != points2.size()) return false;
return true;
}
double triangleArea(Point p1, Point p2, Point p3) {
p1.x -= p3.x;
p2.x -= p3.x;
p1.y -= p3.y;
p2.y -= p3.y;
return (double)p1.x * p2.y - p2.x * p1.y / 2;
}
double computeArea(const vector<Point>& points) {
unsigned int i;
double area;
area = 0;
for (i = 2; i < points.size(); ++i)
area += triangleArea(points[0], points[i - 1], points[i]);
return area;
}
int main() {
FILE *fin, *fout;
fin = fopen("gradina.in", "r");
fout = fopen("gradina.out", "w");
int i, j, k;
double areaDiff, minAreaDiff;
fscanf(fin, "%d", &noPoints);
for (i = 0; i < noPoints; ++i)
fscanf(fin, "%d%d", &points[i].x, &points[i].y);
minAreaDiff = DBL_MAX;
for (i = 0; i < noPoints; ++i)
for (j = i + 1; j < noPoints; ++j) {
printf("%d %d\n", i, j);
splitPoints(points[i], points[j]);
printf("%d %d\n", i, j);
if (checkSplit()) {
areaDiff = abs(computeArea(points1) - computeArea(points2));
if (areaDiff < minAreaDiff)
minAreaDiff = areaDiff;
}
printf("%d %d\n", i, j);
}
fprintf(stdout, "%lf\n", minAreaDiff);
fclose(fin);
fclose(fout);
return 0;
}