Pagini recente » Cod sursa (job #668290) | Cod sursa (job #92254) | Cod sursa (job #1352781) | Cod sursa (job #55994) | Cod sursa (job #2924443)
// TODO: debug lol
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#define double long double
#define int long long
using namespace std;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
namespace Geometry{
struct Point{
double x, y;
};
double dist(Point p1, Point p2){
double dx = p1.x - p2.x, dy = p1.y - p2.y;
return sqrt(dx * dx + dy * dy);
}
double area(Point p1, Point p2, Point p3){
return p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
}
double polygonArea(vector <Point> v){
double A = 0;
int n = (int)v.size();
for(int i = 0; i < n; i++)
A += area(v[i], v[(i + 1) % n], {0, 0});
return A / 2;
}
bool cmp(Point a, Point b){
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
vector <Point> convexHull(vector <Point> v){
int n = (int)v.size();
sort(v.begin(), v.end(), cmp);
vector <Point> up, down;
up.push_back(v[1]);
down.push_back(v[1]);
for(int i = 1; i < n; i++){
while((int)up.size() > 1 && area(up[(int)up.size() - 2], up[(int)up.size() - 1], v[i]) <= 0)
up.pop_back();
up.push_back(v[i]);
while((int)down.size() > 1 && area(down[(int)down.size() - 2], down[(int)down.size() - 1], v[i]) >= 0)
down.pop_back();
down.push_back(v[i]);
}
vector <Point> CH = up;
for(int i = (int)down.size() - 2; i >= 1; i--)
CH.push_back(down[i]);
reverse(CH.begin(), CH.end());
return CH;
}
}
string Min(string a, string b){
for(int i = 0; i < min((int)a.size(), (int)b.size()); i++)
if(a[i] < b[i])
return a;
else if(b[i] < a[i])
return b;
if((int)a.size() < (int)b.size())
return a;
return b;
}
vector <Geometry::Point> v;
signed main(){
int n;
fin >> n;
for(int i = 1; i <= n; i++){
Geometry::Point point;
fin >> point.x >> point.y;
v.push_back(point);
}
// sort(v.begin(), v.end(), Geometry::cmp);
double ans = 1e18;
string sAns = "";
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != j){
vector <Geometry::Point> down, up;
down.push_back(v[i]);
down.push_back(v[j]);
string config1(n + 1, 0), config2(n + 1, 0);
config1[i] = 'I', config1[j] = 'I';
config2[i] = 'V', config2[j] = 'V';
for(int k = 1; k <= n; k++)
if(k != i && k != j){
if(Geometry::area(v[i], v[j], v[k]) <= 0)
down.push_back(v[k]),
config1[k] = 'I', config2[k] = 'V';
else
up.push_back(v[k]),
config1[k] = 'V', config2[k] = 'I';
}
if((int)down.size() > 1 && (int)up.size() > 1){
vector <Geometry::Point> poli1 = Geometry::convexHull(down),
poli2 = Geometry::convexHull(up);
for(auto p : down)
cout << p.x << ' ' << p.y << endl;
double area1 = Geometry::polygonArea(poli1),
area2 = Geometry::polygonArea(poli2);
double diff = abs(area1 - area2);
if(diff < ans){
ans = diff;
sAns = Min(config1, config2);
}else if(diff == ans)
sAns = Min(sAns, Min(config1, config2));
}
}
fout << ans << '\n';
return 0;
}
/*
Eram odata in Padurea Baneasa si am gasit scrijelit pe un copac astfel:
" - Oricare doua poligoane convexe in plan pot fi separate de o dreapta... "
*/