Pagini recente » Cod sursa (job #1174608) | Cod sursa (job #1900750) | Cod sursa (job #1854402) | Cod sursa (job #2091078) | Cod sursa (job #752130)
Cod sursa(job #752130)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream F("dreptunghiuri3.in");
ofstream G("dreptunghiuri3.out");
#define Dmax 1011
#define x first
#define y second
typedef pair<int,int> Point;
Point First[Dmax*10],Second[Dmax*10];
int Value[Dmax*10];
int N,M,K;
int Coord[Dmax*100],Co;
int Coord2[Dmax*100];
int Normx[Dmax*100],Nbrx;
int Normy[Dmax*100],Nbry;
int Val;
int Max;
long long Arie;
int Mat[Dmax*10][Dmax*10];
inline int max(int a,int b)
{ return ( a>b ) ? a : b; }
inline int min(int a,int b)
{ return ( a>b ) ? a : b; }
inline int Calc(int x,int y)
{ return (Normx[x+1]-Normx[x])*(Normy[y+1]-Normy[y]); }
int Bsx(int St,int Dr)
{
if ( St==Dr ) return St;
int Mid=(St+Dr)/2;
if ( Normx[Mid]<Val ) return Bsx(Mid+1,Dr);
if ( Normx[Mid]>Val ) return Bsx(St,Mid-1);
return Mid;
}
int Bsy(int St,int Dr)
{
if ( St==Dr ) return St;
int Mid=(St+Dr)/2;
if ( Normy[Mid]<Val ) return Bsy(Mid+1,Dr);
if ( Normy[Mid]>Val ) return Bsy(St,Mid-1);
return Mid;
}
int main()
{
F>>N>>M>>K;
for (int i=1;i<=K;++i)
{
F>>First[i].x>>First[i].y;
F>>Second[i].x>>Second[i].y;
F>>Value[i];
++Second[i].x;
++Second[i].y;
}
for (int i=1;i<=K;++i)
{
Coord[++Co]=First[i].x;
Coord[++Co]=Second[i].x;
}
sort(Coord,Coord+Co+1);
for (int i=1;i<=Co;++i)
while ( Coord[i]==Coord[i+1] && i<=Co )
Coord[i++]=0;
for (int i=1;i<=Co;++i)
if ( Coord[i] )
Normx[++Nbrx]=Coord[i];
Co=0; for (int i=1;i<=K;++i)
{
Coord2[++Co]=First[i].y;
Coord2[++Co]=Second[i].y;
}
Coord2[Co+1]=0;
sort(Coord2,Coord2+Co+1);
for (int i=1;i<=Co;++i)
while ( Coord2[i]==Coord2[i+1] && i<=Co )
Coord2[i++]=0;
for (int i=1;i<=Co;++i)
if ( Coord2[i] )
Normy[++Nbry]=Coord2[i];
for (int i=1;i<=K;++i)
{
Val=First[i].x;
First[i].x=Bsx(1,Nbrx);
Val=First[i].y;
First[i].y=Bsy(1,Nbry);
Val=Second[i].x;
Second[i].x=Bsx(1,Nbrx);
Val=Second[i].y;
Second[i].y=Bsy(1,Nbry);
}
for (int i=1;i<=K;++i)
{
Mat[First[i].x][First[i].y]+=Value[i];
Mat[Second[i].x][Second[i].y]+=Value[i];
Mat[First[i].x][Second[i].y]-=Value[i];
Mat[Second[i].x][First[i].y]-=Value[i];
}
for (int i=1;i<=Nbrx;++i)
for (int j=1;j<=Nbry;++j)
Max=max(Mat[i][j]=Mat[i][j-1]+Mat[i-1][j]-Mat[i-1][j-1]+Mat[i][j],Max);
Normx[Nbrx+1]=Normx[Nbrx]+1;
Normx[0]=Normx[Nbrx]-1;
Normy[Nbry+1]=Normy[Nbry]+1;
Normy[0]=Normy[Nbry]-1;
for (int i=1;i<=Nbrx;++i)
for (int j=1;j<=Nbry;++j)
Arie+=( Mat[i][j]==Max ) ? Calc(i,j) : 0;
G<<Max<<' '<<Arie<<'\n';
}