Pagini recente » Cod sursa (job #2669342) | Cod sursa (job #338867) | Cod sursa (job #479751) | Cod sursa (job #376291) | Cod sursa (job #845802)
Cod sursa(job #845802)
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <bitset>
using namespace std;
ifstream fi ("pachete.in");
ofstream fo ("pachete.out");
const int dim = 50005;
int N, XC, YC, south;
bitset <dim> viz;
struct punct { long long x, y; int i; } P[dim];
void cit ()
{
fi >> N >> XC >> YC;
south = 1;
for (int i = 1; i <= N; i++)
{
fi >> P[i].x >> P[i].y;
P[i].x -= XC;
P[i].y -= YC;
P[i].i = i;
if (P[south].y > P[i].y || (P[south].y == P[i].y && P[south].x > P[i].x))
south = i;
}
}
int cmp (punct a, punct b)
{
if (a.i == south)
return 1;
if (b.i == south)
return 0;
return a.x * b.y - b.x * a.y > 0;
}
int inclus (punct a, punct b) //return 1 daca b elte intre 0 si a
{
if (b.x < 0)
{
a.x = -a.x;
b.x = -b.x;
}
if (b.y < 0)
{
a.y = -a.y;
b.y = -b.y;
}
return (a.x >= 0 && a.y >= 0 && a.x <= b.x && a.y <= b.y);
}
void parc_st ()
{
int i, pa = 1;
for (i = 2; i <= N; i++)
{
if (inclus (P[i], P[pa]))
viz[i] = 1;
else
pa = i;
}
}
void parc_dr ()
{
int i, pa = 1;
for (i = N; i >= 2; i--)
{
if (inclus (P[i], P[pa]))
viz[i] = 1;
else
pa = i;
}
}
void rez1 ()
{
sort (P+1, P+1+N, cmp);
parc_st ();
parc_dr ();
}
void rez2 ()
{
int i, j;
for (i = 1; i <= N; i++)
viz[i] = 0;
for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
if (i == j)
continue;
if (inclus (P[i], P[j]))
viz[i] = 1;
}
}
}
void afi ()
{
int r = 0;
for (int i = 1; i <= N; i++)
if (viz[i] == 0)
r++;
fo << r << '\n';
}
int main ()
{
cit ();
rez1 ();
afi ();
/*rez2 ();
afi ();*/
return 0;
}