Pagini recente » Monitorul de evaluare | Profil Jordica | Monitorul de evaluare | Diferente pentru utilizator/hopingsteam intre reviziile 20 si 21 | Cod sursa (job #2015544)
#include <cstdio>
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>
#define DIM 200010
#define X first.first
#define Y first.second
#define Z second
#define DIMBUFF 100010
using namespace std;
vector<pair<pair<int, int>, int > >S, J;
int n, x1, x2, y, sol;
stack<int> st;
bitset<DIM> B;
int cmp(const pair<pair<int, int>, int > &a, const pair<pair<int, int>, int > & b) {
long long t = a.X * 1LL * b.Y - a.Y * 1LL * b.X;
if (t == 0)
return a.Z < b.Z;
else
return t < 0;
}
FILE *fin = fopen("rays.in", "r");
ofstream fout("rays.out");
char buff[DIMBUFF];
int pp;
int numar() {
int val = 0, semn;
while (!(buff[pp] >= '0' && buff[pp] <= '9') && buff[pp] != '-') {
pp++;
if (pp == DIMBUFF) {
fread(buff, 1, DIMBUFF, fin);
pp=0;
}
}
if (buff[pp] == '-') {
semn = -1;
pp++;
if (pp == DIMBUFF) {
fread(buff, 1, DIMBUFF, fin);
pp=0;
}
} else {
semn = 1;
}
while (buff[pp] >= '0' && buff[pp] <= '9') {
val = val*10 + buff[pp] - '0';
pp++;
if (pp == DIMBUFF) {
fread(buff, 1, DIMBUFF, fin);
pp=0;
}
}
return val * semn;
}
int main () {
n = numar();
for (int i=1;i<=n;i++) {
//fscanf(fin, "%d %d %d", &y, &x1, &x2);
y = numar();
x1 = numar();
x2 = numar();
if (x1 > x2) {
swap(x1, x2);
}
if (y > 0) {
S.push_back(make_pair(make_pair(x1, y),i));
S.push_back(make_pair(make_pair(x2, y),-i));
}else {
J.push_back(make_pair(make_pair(x1, -y),i));
J.push_back(make_pair(make_pair(x2, -y),-i));
}
}
for (int t = 2; t--;) {
sort(S.begin(), S.end(), cmp);
while (!st.empty())
st.pop();
B.reset();
for (int i=0;i<S.size(); i++) {
int tip = S[i].Z;
if (tip > 0) {
st.push(i);
} else {
if (B[-tip] == 0) {
sol ++;
while (!st.empty()) {
B[ S[st.top()].Z ] = 1;
st.pop();
}
}
}
}
S.clear();
for (int i=0;i<J.size();i++)
S.push_back(J[i]);
}
fout<<sol<<"\n";
return 0;
}