Cod sursa(job #2544592)

Utilizator theo2003Theodor Negrescu theo2003 Data 12 februarie 2020 11:49:42
Problema Rays Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("rays.in");
ofstream cout("rays.out");
struct segment_part {
    long long int x;
    long long int y;
    segment_part *start, *end_;
};
vector<segment_part> left_, right_;
long long int solve(vector<segment_part> &s) {
    sort(s.begin(), s.end(), [](segment_part a, segment_part b) {
        if(a.y*b.x == a.x*b.y)
            return a.start == NULL;
        return a.y*b.x < a.x*b.y;
    });
    long long int return_ = 0;
    pair<long long int, long long int> start = {s[0].x, s[0].y};
    bool empty_ = false;
    for(unsigned int x = 1; x<s.size(); x++) {
        if(s[x].end_ == NULL) {
            if(!empty_ && (s[x].start->y*start.first >= start.second*s[x].start->x)) {
                empty_ = true;
                return_++;
            }
        } else {
            if(empty_){
                start = {s[x].x, s[x].y};
                empty_ = false;
            }
        }
    }
    return return_;
}
int main() {
    //ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int x = 0, a, b, c; x<n; x++) {
        cin>>a>>b>>c;
        if(b > c)
            swap(b, c);
        if(a < 0) {
            left_.push_back(segment_part{-a, b, NULL, NULL});
            left_.push_back(segment_part{-a, c, &left_.back(), NULL});
            left_[left_.size() - 2].end_ = &left_.back();
        } else {
            right_.push_back(segment_part{a, b, NULL});
            right_.push_back(segment_part{a, c, &right_.back()});
            right_[right_.size() - 2].end_ = &right_.back();
        }
    }
    long long int result = solve(left_) + solve(right_);
    cout<<result<<endl;
    return 0;
}