Mai intai trebuie sa te autentifici.
Cod sursa(job #429697)
Utilizator | Data | 30 martie 2010 13:18:36 | |
---|---|---|---|
Problema | Poligon | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Lista lui wefgef | Marime | 5.39 kb |
// Catalin Balan
// Tue Mar 30 09:18:56 EEST 2010
// preONI 2005 - Poligon
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <algorithm>
#include <vector>
using namespace std;
#define NMAX 916
#define FIN "poligon.in"
#define FOUT "poligon.out"
// PARSARE
#define CHUNK 8192
char g_buf[CHUNK];
int g_p=CHUNK-1;
inline int get()
{
int x = 0;
while (g_buf[g_p] < '0' || g_buf[g_p] > '9')
if (++g_p == CHUNK) fread(g_buf,1,CHUNK,stdin), g_p=0;
while (g_buf[g_p] >= '0' && g_buf[g_p] <= '9')
{
x = x*10 + g_buf[g_p]-'0';
if (++g_p == CHUNK) fread(g_buf,1,CHUNK,stdin), g_p=0;
}
return x;
}
// END PARSARE
typedef pair<int, int> pct;
typedef long long i64;
int benzi[NMAX][NMAX]; // benzi[i] contine segmentele ce fac parte din banda i
int vert[NMAX]; // abscisele la care se delimiteaza benzile
pct puncte[NMAX]; // tin minte punctele (X,Y)
pct segm[NMAX]; // tin minte segmentele sub forma de indici de puncte (pct din dr, pct din st)
int ord[NMAX]; // indicii punctelor sortati dupa X
int n,m,k; // k - nr de benzi
int segmVert[NMAX];
double auxComp[NMAX];
bool cmp2( int a, int b )
{
return (puncte[a] < puncte[b]);
}
bool cmp( pct a, pct b )
{
if ( puncte[a.first] == puncte[b.first])
return cmp2(a.second, b.second);
return cmp2(a.first, b.first);
}
bool cmp3( int a, int b )
{
return puncte[segm[a].first].first < puncte[segm[b].first].first;
}
bool cmp4( int a, int b )
{
return (auxComp[a] < auxComp[b]);
}
// vezi daca un punct e deasupra unui segment cu pct a in st si pct b in dr
int deasupra( int x, int y, int xa, int ya, int xb, int yb )
{
if ( y > ya && y > yb) return true;
if ( y < ya && y < yb) return false;
xb -= xa;
yb -= ya;
x -= xa;
y -= ya;
i64 s = (i64)y*(i64)xb - (i64)x*(i64)yb;
if ( s > 0 ) return 1;
if ( s == 0) return 10000;
return 0;
}
int numaraSegm( int x, int y, int banda )
{
vector<int>::iterator it;
int rez = 0;
int st = 1, dr = benzi[banda][0];
while ( st <= dr )
{
int mij = (st+dr)>>1;
int q = deasupra( x, y, puncte[ segm[ benzi[banda][mij] ].first ].first,
puncte[ segm[ benzi[banda][mij] ].first ].second,
puncte[ segm[ benzi[banda][mij] ].second ].first,
puncte[ segm[ benzi[banda][mij] ].second ].second );
if ( q == 10000 ) return 1;
if ( q )
{
rez = mij;
st = mij+1;
} else
dr = mij-1;
}
return rez;
}
int inPoligon( int x, int y )
{
// cauta banda in care e punctul
int st = 0, dr = k;
int ind = 0;
while (st <= dr)
{
int mij = (st+dr)>>1;
if ( x >= vert[mij])
{
ind = mij;
st = mij+1;
} else
dr = mij-1;
}
if (ind == k-1) --ind;
return (numaraSegm( x, y, ind ) & 1);
}
double mijSegm( double xLine, int id )
{
double x1 = puncte[ segm[id].first ].first;
double y1 = puncte[ segm[id].first ].second;
double x2 = puncte[ segm[id].second ].first;
double y2 = puncte[ segm[id].second ].second;
x1-=x2;
y1-=y2;
xLine-=x2;
double yLine = (y1*xLine)/x1;
yLine+=y2;
return yLine;
}
int main(int argv, char ** argc)
{
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
n = get();
m = get();
int x = get();
int y = get();
puncte[1] = make_pair(x,y);
for (int i = 2; i <= n; ++i)
{
int x,y;
x = get();
y = get();
puncte[i] = make_pair(x,y);
if (puncte[i] < puncte[i-1])
segm[i-1] = make_pair(i,i-1);
else segm[i-1] = make_pair(i-1,i);
ord[i] = i;
}
ord[1] = 1;
if (puncte[1] < puncte[n])
segm[n] = make_pair(1,n);
else segm[n] = make_pair(n,1);
sort(segm+1, segm+n+1, cmp);
sort(ord+1, ord+n+1, cmp2);
// delimiteaza benzile
vert[0] = -1;
k = 0;
for (int i = 1; i <= n; ++i)
{
if (puncte[ord[i]].first > vert[k]) vert[++k] = puncte[ord[i]].first;
}
vert[++k] = 100000;
// pune segmentele in benzi
int aux[NMAX], sz = 0;
int j = 1, nrv = 0;
for (int i = 0; i < k; ++i)
{
// scoate elemente
for (int l = 1; l <= sz; ++l)
if ( puncte[ segm[ aux[l] ].second ].first <= vert[i])
{
aux[l] = aux[sz];
--sz;--l;
}
// adauga elemente
while ( j <= n && vert[i+1] > puncte[segm[j].first].first)
{
if (puncte[segm[j].first].first == puncte[segm[j].second].first)
{
segmVert[++nrv] = j;
++j;
continue;
}
aux[++sz] = j;
++j;
}
double midLine = (vert[i]+vert[i+1])>>1;
for ( int l = 1; l <= sz; ++l )
auxComp[aux[l]] = mijSegm( midLine, aux[l] );
sort(aux+1, aux+sz+1, cmp4);
for ( int l = 1; l <= sz; ++l)
benzi[i][l] = aux[l];
benzi[i][0] = sz;
}
sort(segmVert+1, segmVert+nrv+1, cmp3);
/* for (int i = 1; i <= n; ++i)
fprintf(stderr, "%d - %d %d\n", i, puncte[i].first, puncte[i].second);
fprintf(stderr, "\n\n");
for (int i = 1; i <= n; ++i)
fprintf(stderr, "%d - %d %d\n", i, segm[i].first, segm[i].second);
fprintf(stderr, "\n\n");
for (int i = 1; i <= nrv; ++i)
fprintf(stderr, "%d ", segmVert[i]);
fprintf(stderr, "\n");
*/
int rez = 0;
for (;m;--m)
{
x = get();
y = get();
int st = 1, dr = nrv;
int answ = 0;
while (st <= dr)
{
int mij = (st+dr)>>1;
if ( x >= puncte[ segm[ segmVert[mij] ].first ].first )
{
answ = mij;
st = mij+1;
} else
dr = mij-1;
// fprintf(stderr, "%d %d\n", mij, answ);
}
if ( answ && x == puncte[ segm[ segmVert[answ] ].first ].first)
{
if ( y <= puncte[ segm[ segmVert[answ] ].second ].second &&
y >= puncte[ segm[ segmVert[answ] ].first ].second )
{
++rez;
continue;
}
}
rez += inPoligon(x,y);
//fprintf(stderr, "%d\n", rez);
}
printf("%d\n", rez);
return EXIT_SUCCESS;
}