1

#include <bits/stdc++.h>
using namespace std;
int t, n;
char c;
long double x, y;
struct point {
    long double x, y;
};
vector<point> Points;
long double crossProduct(point A, point B) { return A.x * B.y - A.y * B.x; }
long double distance(point A, point B) { return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)); }
bool compare(point A, point B, point o) {
    A.x -= o.x, A.y -= o.y, B.x -= o.x, B.y -= o.y;
    long double tmp = crossProduct(A, B);
    if (tmp > 0)
        return true;
    else if (tmp == 0)
        return distance(A, { 0, 0 }) < distance(B, { 0, 0 });
    else
        return false;
}
bool cmp(point a, point b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
bool cmp2(point a, point b) { return compare(a, b, Points[0]); }
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {

            cin >> x >> y >> c;
            if (c == 'Y') Points.push_back({ x, y });
        }
        cout << Points.size() << '\n';
        sort(Points.begin(), Points.end(), cmp);
        sort(Points.begin() + 1, Points.end(), cmp2);
        for (point p : Points) printf("%.0f %.0f\n", p.x, p.y);
    }
    return 0;
}

2

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, ans, now;
double s;
int x[N], y[N], v[N], l[N];
struct point { int x, y; };
double dist(point a, point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
double convexHullPerimeter(vector<point>& points) {
    int n = points.size();
    vector<point> convexHull;
    sort(points.begin(), points.end(), [](point a, point b) {
        return (a.x != b.x) ? a.x < b.x : a.y < b.y;
    });

    for (int i = 0; i < 2; ++i) {
        int start = convexHull.size();
        for (const point& p : points) {
            while (convexHull.size() >= start + 2 && (convexHull[convexHull.size() - 2].x - convexHull[convexHull.size() - 1].x) * (p.y - convexHull[convexHull.size() - 1].y) - (convexHull[convexHull.size() - 2].y - convexHull[convexHull.size() - 1].y) * (p.x - convexHull[convexHull.size() - 1].x) <= 0) {
                convexHull.pop_back();
            }
            convexHull.push_back(p);
        }
        convexHull.pop_back();
        reverse(points.begin(), points.end());
    }
    double perimeter = 0.0;
    for (int i = 0; i < convexHull.size(); ++i) {
        perimeter += dist(convexHull[i], convexHull[(i + 1) % convexHull.size()]);
    }
    return perimeter;
}

int main() {
    int cnt = 1;
    while (cin >> n && n) {
        now = 2e9;
        for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> v[i] >> l[i];
        for (int i = 0; i < (1 << n) - 1; i++) {
            vector <point> ve;
            int sumv = 0, suml = 0;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) { // kill
                    sumv += v[j];
                    suml += l[j];
                } else {
                    ve.push_back({x[j], y[j]});
                }
            }
            double c = convexHullPerimeter(ve);
            if (suml >= c && now > sumv) now = sumv, ans = i, s = suml - c;
        }
        cout << "Forest " << cnt++ << '\n';
        cout << "Cut these trees: ";
        for (int i = 0; i < n; i++) if (ans & (1 << i)) cout << " " << i + 1;
        cout << "\nExtra wood: " << s << '\n';

    }
    return 0;
}