Cod sursa(job #2878145)

Utilizator DooMeDCristian Alexutan DooMeD Data 25 martie 2022 21:24:57
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
using namespace std;

struct Point {
	double x, y;
	double operator*(const Point & other) {
		return x*other.y - other.x*y;
	}
};

bool comp(Point a, Point b) {
	if(a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

bool crease(Point New, Point Old, Point Origin) {
	New.x -= Origin.x, New.y -= Origin.y;
	Old.x -= Origin.x, Old.y -= Origin.y;
	return (New*Old)<0;
}

int main() {
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	
	Point A; A.x = 1; A.y = 3;
	Point B; B.x = 0; B.y = 2;
	Point C; C.x = 0; C.y = 4;
	crease(A,B,C);
	int n; f >> n;
	vector<Point> v(n);
	for(int i=0; i<n; i++) f >> v[i].x >> v[i].y;
	sort(v.begin(), v.end(), comp);
	vector<Point> st;
	for(int temp=0; temp<2; temp++) {
		for(int i=temp; i<n-temp; i++) {
			while(st.size()>=2 and crease(v[i], st[st.size()-2], st[st.size()-1])) st.pop_back();
			st.emplace_back(v[i]);
		}
		reverse(v.begin(), v.end());
	}
	g << st.size() << "\n";
	for(auto i : st) g << i.x << " " << i.y << "\n";
	return 0;
}