Pagini recente » Cod sursa (job #751117) | Cod sursa (job #350821) | Cod sursa (job #2490248) | Cod sursa (job #2775907) | Cod sursa (job #918799)
Cod sursa(job #918799)
#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
#include <utility>
using namespace std;
#define INF 1e15
#define MAXN 255
struct Point { int x, y;}; int N;Point P[MAXN];int idx[MAXN];int FIRST;int st[MAXN];int head;bool v[MAXN];char distr1[MAXN], distr2[MAXN];string minDistr; long long crossProduct(const Point &A, const Point &B, const Point &C) { return (long long)(B.x - A.x) * (C.y - A.y) - (long long)(B.y - A.y) * (C.x - A.x);} bool cmp(const int &A, const int &B) { return P[A].y < P[B].y || (P[A].y == P[B].y && P[A].x < P[B].x);} void convexHull(vector<int> &pts, vector<int> &R) { if(pts.size() < 3) return; st[0] = pts[0]; st[1] = pts[1]; v[pts[1]] = true; head = 1; for(size_t i = 2; i < pts.size(); i++) { if(v[pts[i]]) continue; while(head >= 1 && crossProduct(P[st[head - 1]], P[st[head]], P[pts[i]]) < 0) { v[st[head]] = false; head--; } v[pts[i]] = true; st[++head] = pts[i]; } for(int i = (int)pts.size() - 1; i >= 0; i--) { if(v[pts[i]]) { v[pts[i]] = false; continue; } while(head >= 1 && crossProduct(P[st[head - 1]], P[st[head]], P[pts[i]]) < 0) { v[st[head]] = false; head--; } st[++head] = pts[i]; } for(int i = 0; i < head; i++) R.push_back(st[i]);} long long ariePoligon(vector<int> &pts) { long long ret = 0; for(size_t i = 1; i + 1 < pts.size(); i++) { long long cp = crossProduct(P[pts[0]], P[pts[i]], P[pts[i + 1]]); ret += cp; } return abs(ret);} string getDistr(vector<int> P[2]) { for(int i = 0; i < 2; i++) for(size_t j = 0; j < P[i].size(); j++) { if(i == 0) { distr1[P[i][j]] = 'I'; distr2[P[i][j]] = 'V'; } else { distr1[P[i][j]] = 'V'; distr2[P[i][j]] = 'I'; } } string v1(distr1); string v2(distr2); return min(v1, v2);} int main() { freopen("gradina.in", "r", stdin); freopen("gradina.out","w", stdout); scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%d %d", &P[i].x, &P[i].y); for(int i = 0; i < N; i++) idx[i] = i; sort(idx, idx + N, cmp); long long minDiff = INF; for(int x = 0; x < N; x++) for(int y = 0; y < N; y++) if(x != y) { vector<int> sp[2]; for(int i = 0; i < N; i++) { if(i == x) sp[0].push_back(idx[x]); else if(i == y) sp[1].push_back(idx[y]); else { long long cp = crossProduct(P[idx[x]], P[idx[y]], P[idx[i]]); int side = (cp > 0); sp[side].push_back(idx[i]); } } vector<int> inf[2]; convexHull(sp[0], inf[0]); if(sp[0].size() != inf[0].size()) continue; convexHull(sp[1], inf[1]); if(sp[1].size() != inf[1].size()) continue; long long arie[2]; arie[0] = ariePoligon(inf[0]); arie[1] = ariePoligon(inf[1]); long long diff = arie[0] - arie[1]; if(diff < 0) diff = -diff; if(diff < minDiff) { minDiff = diff; minDistr = getDistr(inf); } else if(diff == minDiff) { string s = getDistr(inf); if(s < minDistr) minDistr = s; } } printf("%.1lf\n", (double)minDiff / 2.0); printf("%s\n", minDistr.c_str()); return 0;}