Pagini recente » Autentificare | Cod sursa (job #194680) | oji-9-10-1 | Cod sursa (job #264297) | Cod sursa (job #2017354)
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <vector>
#include <stack>
#define x first.first
#define y first.second
#define z second
#define DIM 200001
#define DIMBUFF 100001
using namespace std;
FILE *fin = fopen("rays.in", "r");
FILE *fout = fopen("rays.out", "w");
int n,x1,x2,y1,sol,i;
vector < pair < pair <int, int>, int > > sus, jos;
stack <int> st;
bitset <DIM> v;
int cmp(pair < pair <int, int>, int > a, pair < pair <int, int>, int > b)
{
long long t = a.x*b.y-a.y*b.x;
if (t == 0)
return a.z < b.z;
else
return t < 0;
}
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 (i=1; i<=n; i++)
{
y1 = numar();
x1 = numar();
x2 = numar();
if (x1 > x2)
swap(x1, x2);
if (y1 > 0)
{
sus.push_back(make_pair(make_pair(x1, y1),i));
sus.push_back(make_pair(make_pair(x2, y1),-i));
}
else
{
jos.push_back(make_pair(make_pair(x1, -y1),i));
jos.push_back(make_pair(make_pair(x2, -y1),-i));
}
}
int T = 2;
for (;T--;)
{
sort(sus.begin(), sus.end(), cmp);
while (!st.empty())
st.pop();
v.reset();
for (int i=0;i<sus.size(); i++)
{
if (sus[i].z > 0)
st.push(i);
else
if (v[-sus[i].z] == 0)
{
sol++;
while (!st.empty())
{
v[sus[st.top()].z] = 1;
st.pop();
}
}
}
sus.clear();
for (i=0; i<jos.size(); i++)
sus.push_back(jos[i]);
}
fprintf(fout, "%d", sol);
return 0;
}