Pagini recente » Borderou de evaluare (job #349968) | Cod sursa (job #944742) | Cod sursa (job #1342705) | Cod sursa (job #1945301) | Cod sursa (job #3188923)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <bitset>
#include <stack>
#define DIM 200001
using namespace std;
ifstream fin("rays.in");
ofstream fout("rays.out");
int n,x,y1,y2;
vector<pair<pair<int,int>,int>> st,dr;
stack<int> s;
bitset<DIM> f;
bool cmp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b) {
long long aux=1LL*a.first.first*b.first.second-1LL*a.first.second*b.first.first;
if (aux==0)
return a.second<b.second;
return aux<0;
}
int calc(vector<pair<pair<int,int>,int>> v) {
int cnt=0;
sort(v.begin(),v.end(),cmp);
while (!s.empty())
s.pop();
f.reset();
for (int i=0;i<v.size();i++) {
int tip=v[i].second;
if (tip>0)
s.push(i);
else
if (f[-tip]==0) {
cnt++;
while (!s.empty()) {
f[v[s.top()].second]=1;
s.pop();
}
}
}
return cnt;
}
int main() {
fin>>n;
for (int i=1;i<=n;i++) {
fin>>x>>y1>>y2;
if (y1>y2)
swap(y1,y2);
if (x>0) {
st.push_back({{y1,x},i});
st.push_back({{y2,x},-i});
}
else {
dr.push_back({{y1,-x},i});
dr.push_back({{y2,-x},-i});
}
}
fout<<calc(st)+calc(dr);
return 0;
}