Cod sursa(job #2779435)

Utilizator bubblegumixUdrea Robert bubblegumix Data 3 octombrie 2021 19:15:07
Problema Rays Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<unordered_set>
#include<cmath>
#include<unordered_map>
#include<vector>
#include<climits> 
#define feach(it,v) for(auto& it : v)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define hmap unordered_map 
#define hset unordered_set
#define inf 0x3f3f3f3f
#define inrange(x,a,b) (x>=a && x<=b)
using namespace std;
typedef long long ll;
vector<pair<double, double>> r_seg;
vector<pair<double, double>> l_seg;
ifstream f("rays.in");
ofstream g("rays.out");
int n;

int baleiere(vector<pair< double, double>>&sgm)
{
	int gloante = 0;
	double ray = sgm.begin()->first - 1;
	feach(i, sgm)
	{
		if (ray < i.first)
		{
			gloante++;
			ray = i.second;
		}
		else
			ray = min(ray, i.second);
	}
	return gloante;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	f >> n;
	for (int i = 1; i <= n; i++)
	{
		int x, y1, y2;
		f >> x >> y1 >> y2;
		if (y1 > y2)
			swap(y1, y2);
		if (x < 0)
			l_seg.push_back(make_pair(atan2(y1,-x),atan2(y2,-x)));
		else
			r_seg.push_back(make_pair( atan2(y1,x),atan2(y2,x) ));
		
		
	}
	sort(all(l_seg));
	sort(all(r_seg));  
	g << baleiere(l_seg) + baleiere(r_seg);
}