Pagini recente » Cod sursa (job #3189925) | Cod sursa (job #457153) | Cod sursa (job #937957) | Cod sursa (job #1343268) | Cod sursa (job #415407)
Cod sursa(job #415407)
#include<fstream>
#include<algorithm>
#include<vector>
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,first,second,step,band,rez,weird;
long long area(point a,point b,point c)
{
long long areax=1LL*a.first*(b.second-c.second)+1LL*b.first*(c.second-a.second)+1LL*c.first*(a.second-b.second);
return areax;
}
bool fcomp(const line& a,const line& b)
{
if(a.first<a.second)
return (area(a.first,a.second,b.second)>=0);
return (area(a.second,a.first,b.second)>=0);
}
int main()
{
f>>n>>m;
for(i=1;i<=n;++i)
f>>a[i].first>>a[i].second,a[i].first*=2,a[i].second*=2,b[i]=a[i];
sort(b+1,b+n+1);
for(i=1;i<=n;++i)
E[i].second=b[i].first;
E[0].second=-1;
E[n+1].second=70000;
a[0]=a[n];
/*for(i=0;i<n;++i)
for(j=1;j<=n;++j)
if(a[i].first!=a[i+1].first)
if((a[i].first<=E[j].second&&a[i+1].first>=E[j+1].second)||(a[i+1].first<=E[j].second&&a[i].first>=E[j+1].second))
E[j].first.push_back(make_pair(a[i],a[i+1]));*/
for(i=0;i<=n;++i)
E[i].first.push_back(make_pair(make_pair(-1,-1),make_pair(70000,-1)));
for(i=1;i<=n;++i)
sort(E[i].first.begin(),E[i].first.end(),fcomp);
for(i=0;i<=n;++i)
{
g<<"Banda:"<<i<<"\n";
for(vector<line>::iterator it=E[i].first.begin();it!=E[i].first.end();++it)
g<<it->first.first<<" "<<it->first.second<<" "<<it->second.first<<" "<<it->second.second<<"\n";
g<<"\n";
}
/* for(i=1;i<=m;++i)
{
f>>first>>second;
first*=2;
second*=2;
for(step=1;step<n;step<<=1);
for(j=0;step;step>>=1)
if(j+step<=n&&E[j+step].second<=first)
j+=step;
band=j;
if(band==n&&first==E[band].second)
--band;
for(step=1;step<E[band].first.size();step<<=1);
weird=E[band].first.size();
for(j=0;step;step>>=1)
if(j+step<E[band].first.size()&&fcomp(E[band].first[j+step],make_pair(make_pair(first,second),make_pair(first,second))))
j+=step;
if((j&1)==0)
if(j<weird&&area(min(E[band].first[j].first,E[band].first[j].second),max(E[band].first[j].first,E[band].first[j].second),make_pair(first,second))==0)
++rez;
else;
else
++rez;
}*/
g<<rez<<"\n";
f.close();
g.close();
return 0;
}