Cod sursa(job #2878156)

Utilizator DooMeDCristian Alexutan DooMeD Data 25 martie 2022 21:54:29
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 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 A, Point B, Point C) {
	B.x -= A.x; B.y -= A.y;
	C.x -= A.x; C.y -= A.y;
	return (B*C) > 0;	
}	
 
int main() {
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	
	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);
	int mne = 1, mxe = 1;
	int ind = 1;
	while(ind<v.size() and v[ind].x==v[ind-1].x) mne++, ind++;
	ind = n-2;
	while(ind>=0 and v[ind].x==v[ind+1].x) mxe++, ind--;
	vector<Point> st;
	for(int i=0; i<n; i++) {
		while(st.size()>=2 and crease(st[st.size()-2], v[i], st[st.size()-1])) 
			st.pop_back();
		st.push_back(v[i]);
	}
	for(int i=n-mxe-1; i>mne; i--) {
		while(st.size()>=2 and crease(st[st.size()-2], v[i], st[st.size()-1]))
			st.pop_back();
		st.push_back(v[i]);
	}
	g << st.size() << "\n";
	for(auto i : st) g << fixed << setprecision(12) << i.x << " " << i.y << "\n";
	return 0;
}