Pagini recente » Cod sursa (job #1013503) | Cod sursa (job #2626926) | Cod sursa (job #530696) | Cod sursa (job #1974244) | Cod sursa (job #2586711)
#include <bits/stdc++.h>
#define NMAX 2050
using namespace std;
ifstream fin("canibali.in");
ofstream fout("canibali.out");
struct tip{int x,y,z,t;};
tip v[NMAX];
vector<int>g[2*NMAX];
int n;
bool ok=1;
bool uz[2*NMAX];
int st[2*NMAX];
int dr[2*NMAX];
void citire();
bool cup(int k);
bool compar1(int i, int j)
{
tip a=v[i];
tip b =v[j];
return a.x>=b.x && a.y>=b.y && a.z>=b.z && a.t>=b.t;
}
bool compar(tip a, tip b)
{
return a.x<b.x || a.x==b.x && a.y<b.y || a.x==b.x && a.y==b.y && a.z<b.z || a.x==b.x && a.y==b.y && a.z==b.z && a.t<b.t ;
}
int main()
{citire();
while(ok)
{
int i;
ok=0;
memset(uz,0,sizeof(uz));
for(i=1;i<=n;i++)
if(!uz[i] && !st[i])
{
ok|=cup(i);
}
}
int sol=0;
for(int i=1;i<=n;i++)
if(st[i] )
sol++;
fout<<n/2-sol;
return 0;
}
void citire()
{int i,j;
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y>>v[i].z>>v[i].t;
sort(v+1,v+n+1,compar);
for(i=2;i<=n;i++)
for(j=1;j<=i-1;j++)
{
if( compar1(i,j) )
{
g[i].push_back(j);
g[i+n].push_back(j);
}
}
n*=2;
}
bool cup(int k)
{int i;
if(uz[k])
return 0;
uz[k]=1;
for(i=0;i<g[k].size();i++)
{
int vec=g[k][i];
if(!dr[vec])
{
st[k]=vec;
dr[vec]=k;
return 1;
}
}
for(i=0;i<g[k].size();i++)
{
int vec=g[k][i];
if(cup(dr[vec]) )
{
st[k]=vec;
dr[vec]=k;
return 1;
}
}
return 0;
}