Pagini recente » Cod sursa (job #2334435) | Cod sursa (job #133563) | Cod sursa (job #110824) | Cod sursa (job #613831) | Cod sursa (job #415390)
Cod sursa(job #415390)
#include<fstream>
#include<algorithm>
#include<vector>
#define x first
#define y second
using namespace std;
const char iname[]="poligon.in";
const char oname[]="poligon.out";
const int maxn=1605;
ifstream f(iname);
ofstream g(oname);
typedef pair<int,int> point;
typedef pair<point,point> line;
point a[maxn],b[maxn];
pair<vector<line>,int> E[maxn];
vector<line> aux;
int i,j,n,m,x,y,step,band,rez,weird;
long long area(point a,point b,point c)
{
long long areax=1LL*a.x*(b.y-c.y)+1LL*b.x*(c.y-a.y)+1LL*c.x*(a.y-b.y);
return areax;
}
bool fcomp(const line& a,const line& b)
{
if(a.x<b.x)
return true;
else
return false;
if(a.x<a.y)
return area(a.x,a.y,b.y)>=0;
return area(a.y,a.x,b.y)>=0;
}
int main()
{
f>>n>>m;
for(i=1;i<=n;++i)
f>>a[i].x>>a[i].y,a[i].x*=2,a[i].y*=2,b[i]=a[i];
sort(b+1,b+n+1);
for(i=1;i<=n;++i)
E[i].y=b[i].x;
E[0].y=-1;
E[n+1].y=70000;
a[0]=a[n];
for(i=0;i<n;++i)
for(j=1;j<=n;++j)
if(a[i].x!=a[i+1].x)
if((a[i].x<=E[j].y&&a[i+1].x>=E[j+1].y)||(a[i+1].x<=E[j].y&&a[i].x>=E[j+1].y))
E[j].x.push_back(make_pair(a[i],a[i+1]));
for(i=0;i<=n;++i)
E[i].x.push_back(make_pair(make_pair(-1,-1),make_pair(70000,-1)));
for(i=1;i<=n;++i)
sort(E[i].x.begin(),E[i].x.end(),fcomp);
/* for(i=1;i<=n;++i)
{
g<<"Banda:"<<i<<"\n";
for(vector<line>::iterator it=E[i].x.begin();it!=E[i].x.end();++it)
g<<it->x.x<<" "<<it->x.y<<" "<<it->y.x<<" "<<it->y.y<<"\n";
g<<"\n";
}*/
/* for(i=1;i<=m;++i)
{
f>>x>>y;
x*=2;
y*=2;
for(step=1;step<n;step<<=1);
for(j=0;step;step>>=1)
if(j+step<=n&&E[j+step].y<=x)
j+=step;
band=j;
if(band==n&&x==E[band].y)
--band;
for(step=1;step<E[band].x.size();step<<=1);
weird=E[band].x.size();
for(j=0;step;step>>=1)
if(j+step<E[band].x.size()&&fcomp(E[band].x[j+step],make_pair(make_pair(x,y),make_pair(x,y))))
j+=step;
if((j&1)==0)
if(j<weird&&area(min(E[band].x[j].x,E[band].x[j].y),max(E[band].x[j].x,E[band].x[j].y),make_pair(x,y))==0)
++rez;
else;
else
++rez;
}*/
g<<rez<<"\n";
f.close();
g.close();
return 0;
}