Cod sursa(job #3032232)

Utilizator BadHero112Ursu Vasile BadHero112 Data 21 martie 2023 19:10:58
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=120001;
using namespace std;

int n;
struct punct{
	double x;
	double y;
	
	bool operator == (punct &X){
		return x==X.x&&y==X.y;
	}
	
}A[maxn];

punct colt;

bool compare(punct A,punct B){
	double cosA=(A.x-colt.x)/sqrtl((A.x-colt.x)*(A.x-colt.x)+(A.y-colt.y)*(A.y-colt.y));
	double cosB=(B.x-colt.x)/sqrtl((B.x-colt.x)*(B.x-colt.x)+(B.y-colt.y)*(B.y-colt.y));
	return cosA>cosB;
}

int main(){
	ifstream cin("infasuratoare.in");
	ofstream cout("infasuratoare.out");
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>A[i].x;
		cin>>A[i].y;
	}
	colt.y=A[0].y;
	colt.x=A[0].x;
	for(int i=1;i<n;i++){
		if(A[i].y<colt.y){
			colt=A[i];
		}
		else if(A[i].y==colt.y){
			if(A[i].x<colt.x)A[i]=colt;
		}
	}
	for(int i=0;i<n;i++){
		if(A[i]==colt){
			for(;i<n-1;i++){
				A[i]=A[i+1];
			}
		}
	}
	sort(A,A+n-1,compare);
	vector<punct> S;
	S.push_back(colt);
	S.push_back(A[0]);
	for(int i=1;i<n-1;i++){
		while(((S[S.size()-1].x-A[i].x)*(S[S.size()-2].y-A[i].y)-(S[S.size()-1].y-A[i].y)*(S[S.size()-2].x-A[i].x))>0)S.pop_back();
		S.push_back(A[i]);
	}
	cout<<S.size()<<endl;
	for(int i=0;i<S.size();i++)cout<<S[i].x<<" "<<S[i].y<<endl;
}