Pagini recente » Cod sursa (job #2337056) | Cod sursa (job #847664) | Cod sursa (job #682914) | Cod sursa (job #1356689) | Cod sursa (job #1372240)
#include <cstdio>
#include <algorithm>
#include <cmath>
#define NMAX 10010
#define INF 2000000000
using namespace std;
struct pack{
int x, y;
double u, r;
};
struct pack P[NMAX], S[NMAX];
int n, sol;
void citire ();
void rez ();
void ordoneaza ();
int pi (struct pack, struct pack, struct pack);
bool comp (struct pack, struct pack);
void afisare();
int main()
{
citire();
rez();
afisare();
return 0;
}
void citire()
{
int i;
FILE*fin=fopen ("infasuratoare.in", "r");
fscanf(fin, "%d", &n);
for (i=1; i<=n; ++i)
fscanf(fin, "%d %d", &P[i].x, &P[i].y);
fclose(fin);
return;
}
void rez()
{
int i, vf, prod;
ordoneaza();
S[1]=P[1]; S[2]=P[2];
vf=2;
for (i=3; i<=n; ++i)
{
prod=pi(S[vf-1], S[vf], P[i]);
if (!prod)//atunci S[vf] si P[i] au aceleasi unghiuri polare fata de P[1]
{
//il retin doar pe cel mai indepartat, adica P[i]
--vf;
S[++vf]=P[i];
}
else
if (prod>0)//intoarcere la stanga
S[++vf]=P[i];
else
{
//nu-i bun
while (vf>1 && prod<=0)
{
--vf;
prod=pi(S[vf-1], S[vf], P[i]);
}
S[++vf]=P[i];
}
}
sol=n-vf;
return;
}
void ordoneaza()
{
struct pack aux;
int i, ymin=INF, xmin=INF, minimus;
for (i=1; i<=n; ++i)
if (P[i].y<ymin || (ymin==P[i].y && P[i].x<xmin))
{
minimus=i;
ymin=P[i].y;
xmin=P[i].x;
}
aux=P[1];
P[1]=P[minimus];
P[minimus]=aux;
for (i=2; i<=n; ++i)
{
P[i].u=atan((double)(P[i].y-P[1].y)/(P[i].x-P[1].x));
P[i].r=sqrt((double)(P[i].y-P[1].y)*(P[i].y-P[1].y)+(P[i].x-P[1].x)*(P[i].x-P[1].x));
}
sort (P+2, P+n+1, comp);
return;
}
bool comp (struct pack a, struct pack b)
{
return a.u<b.u || (a.u==b.u && a.r<b.r);
}
int pi (struct pack a, struct pack b, struct pack c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
//returneaza o val. pozitiva daca in b-c se face o intoarcere la stanga
//respectiv o val. negativa daca in b-c se face o intoarcere la dreapta
void afisare()
{
FILE*fout=fopen ("infasuratoare.out", "w");
fprintf(fout, "%d\n", sol);
fclose(fout);
return;
}