fork(3) download

copy

/* BDFHJK
 * Version : trunk
 * Wed, 15 Jun 2011 19:58:49 +0200 */
 
#include<iostream>
#include<cstdio>
#include<string>
#include<list>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<utility>
#include<sstream>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<sys/time.h>
 
///Train mode
#include<fstream>
 
using namespace std;
 
//#define DEBUG 1
#define NORMAL 1
//#define TRAIN 1
//#define VISUAL 1
 
#define DB(X) printf("Debug: %d\n", X);
 
#define REP(I,N) for(int I=0;I<(N);I++)
#define FOR(I,A,B) for(int I=(A);I<=(B);I++)
#define FORD(I,A,B) for(int I=(A);I>=(B);I--)
#define ALL(X) (X).begin(),(X).end()
#define FOREACH(I,C) for(VAR(I,(C).begin());I!=(C).end();I++)
 
#define MOD ((int)1e9+7)
#define INF ((int)1e9+7)
#define mINF ((int)1e6+7)
#define EPS 1e-1
#define PI ((LD)3.141592654)
 
#define VAR(V,init) __typeof(init) V=(init)
#define SIZE(X) X.size()
 
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
 
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef long long LL;
typedef vector<string> VS;
typedef long double LD;
 
LL nwd(LL a, LL b) { return !b?a:nwd(b,a%b); }
 
double czas;
 
static inline double gT2(){
    timeval tv;
    gettimeofday(&tv, 0);
    return tv.tv_sec + tv.tv_usec * 1e-6;
}
 
static double startTime;
 
static inline void initTime(){
    startTime = gT2();
}
 
static inline bool isTimeup() {
    return czas <= gT2() - startTime;
}
 
 
VS R;
unsigned char P[2000][2000];
int W, H;
string name;
bool used[1500][1500];
bool crat[1500][1500]; 
int kwadrat_size;
int kwadrat_sum;
int light;
int frag_light;
int lights[20][20];
int TM;
int GxM[3][3];
int GyM[3][3];		
int gM[5][5];		    
unsigned char PE[20][1500][1500]; ///20*2*2*MB=80MB
int eD[1500][1500];			
double grd[1500][1500];    
int uTh;
int lTh;
int UT;
 
int ZA;
 
typedef struct
{
    string name;
    int minx;
    int maxx;
    int miny;
    int maxy;
    int pole;
    int probe;
    int algo;
    int cx;
    int cy;
    LD ratio2;		///Circle to center frag from algo 2
    LD frag; 		///Black pixels frag
    LD crater;		///Num of black pixels
    LD black;		///Num of more than black pixels
    LD ultrablack;   
    LD differ;    	///Differ of black pixels
    LD sldp;		///Left to right sum of pixels
    LD score;		
    LD ratio;		///Center to circle diff from algo 1
    LD fraci;		///Frag on circle from calc
    LD cendiff;
    LD corndiff;	
    LD cenfra;
    LD cornfra;
    LD frd;    
    LD rzp; 		///Rozproszenie
    LD cratincircle;
    LD bestcirc;
    vector<int> fragmenty;
    bool md;
    bool uniq;
} rectangle;
 
typedef struct
{
    string name;
    bool used;
    vector<rectangle> rectangles;
} answer;
vector<answer> answers;
vector<rectangle> AA;
vector<rectangle> BB;
vector<rectangle> CC;
 
struct crcmp
{
    bool operator () (const rectangle &l, const rectangle &p) const
    {
        if (l.score < p.score) return true;
        else return false;
    }
} crc;
 
int ZI;
 
class CraterDetection
{
    public:
 
    bool overlap(rectangle a, rectangle b) 
    {
		int xl, xr, yt, yb, arA, arB, iA, uA;
        arA = (a.maxx - a.minx + 1) * (a.maxy - a.miny + 1);
        arB = (b.maxx - b.minx + 1) * (b.maxy - b.miny + 1);
		xl = max(a.minx, b.minx);
        xr = min(a.maxx, b.maxx);
        yt = max(a.miny, b.miny);
        yb = min(a.maxy, b.maxy);
		iA = (xl <= xr && yt <= yb ? (xr - xl + 1) * (yb - yt + 1) : 0);
        uA = arA + arB - iA;
 
        return 10 * iA > 3 * uA;
    }    
    void calc_answers()
    {
        int anscnt = 0;
        int goodans = 0;
        int badans = 0;
        int unique = 0;
        int uniqueTM0 = 0;
        int uniqueTM1 = 0;
        int uniqueTM2 = 0;
        int uniqueTM3 = 0;
        int uniqueTM4 = 0;
        int uniqueTM5 = 0;
        int uniqueTM6 = 0;
        int uniqueTM7 = 0;
        int anTM[11]; 
        int negTM[11]; 
        int good[900];
        int bad[900];
 
        memset(anTM, 0, sizeof(anTM)); 
        memset(negTM, 0, sizeof(negTM)); 
        memset(good, 0, sizeof(good)); 
        memset(bad, 0, sizeof(bad)); 
 
 
 
        REP(i, AA.size()) 
        {
            bool pass = 0;
            REP(j, answers.size()) REP(k, answers[j].rectangles.size())
            {
 
                if (AA[i].name == answers[j].name)
                {
                    if (overlap(AA[i], answers[j].rectangles[k]))
                    {
                        if (pass == 0)
                        {
                            anTM[AA[i].probe]++;
                            goodans++;
                            pass = 1;
                            AA[i].md = 1;
                        }
                        if (answers[j].rectangles[k].md == 0)
                        {
							good[i/100]++;
							AA[i].uniq = 1;
							answers[j].rectangles[k].md = 1;
                            unique++;
                            if (AA[i].probe == 0) uniqueTM0++; 
                            if (AA[i].probe == 1) uniqueTM1++;
                            if (AA[i].probe == 2) uniqueTM2++;
                            if (AA[i].probe == 3) uniqueTM3++;
                            if (AA[i].probe == 4) uniqueTM4++;
                            if (AA[i].probe == 5) uniqueTM5++;
                            if (AA[i].probe == 6) uniqueTM6++;
                            if (AA[i].probe == 7) uniqueTM7++;
                        }
 
                    }else
                    {
 
                    }
                }
            }
 
            if (pass == 0)
            {
                negTM[AA[i].probe]++;
                badans++;                
                bad[i/100]++;
            }
        }
 
        cerr << "----------------CRATERS FOUND------------" << endl;
 
        int zak = 0;
        FOR(i, 0, AA.size()-1)
        {
            if (zak < 100)
            {
                if (AA[i].md == 0) 
                {
					cerr << "*FAUL*" << endl;
				}else if (AA[i].uniq == 0) cerr << "*REPEAT*" << endl;
                cerr << AA[i].name << " ==>  SCORE = " << AA[i].score << " NX = " << AA[i].minx << " MX = " << AA[i].maxx << " NY = " << AA[i].miny << " MY " << AA[i].maxy << endl;
                cerr << "FRAG = " << AA[i].frag << " DIFF = " << AA[i].differ << " CRATER = " << AA[i].crater << " SLDP = " << AA[i].sldp << " RATIO = " << AA[i].ratio << " FRACI = " << AA[i].fraci << endl;
                cerr << "CORNDIFF = " << AA[i].corndiff << " CENTEDIFF = " << AA[i].cendiff <<  " CENFRA = " << AA[i].cenfra << " CORNFRA = " << AA[i].cornfra << " FRD = " << AA[i].frd << endl;
                cerr << "BLACK = " << AA[i].black << " ULTRABLACK = " << AA[i].ultrablack << " RZP = " << AA[i].rzp << " CX = " << AA[i].cx << " CY = " << AA[i].cy << " CICR = " << AA[i].cratincircle << " MXCIR = " << AA[i].bestcirc;
                if (AA[i].fragmenty.size() > 0)
                {
					REP(f, AA[i].fragmenty.size()) cerr << " F" << f << "= " << AA[i].fragmenty[f];
				}
				cerr << endl;
                cerr << endl;
                zak++; 
            }
        }
 
        cerr << "-----------------CRATERS NOT FOUND--------------" << endl;
 
        zak = 0;
        REP(j, answers.size()) REP(k, answers[j].rectangles.size())
        {
			if (zak > 100 || answers[j].used==0) continue;
			if (answers[j].rectangles[k].md == 0) 
			{
				rectangle RC = answers[j].rectangles[k];
				cerr << "NAME = " << answers[j].name << " NX = " << RC.minx << " MX = " << RC.maxx << " NY = " << RC.miny << " MY " << RC.maxy << endl;
				cerr << endl;
				zak++;
			}
		}
 
		cerr << endl;
 
 
        cerr << "--------------------STAT------------------------" << endl;
        REP(i, AA.size()/100) 
        {
			double gb = (bad[i]==0) ? 0 : ((LD)good[i]/(LD)bad[i]);
			cerr << "ZAKR = " << (i*100) << " - " << ((i+1)*100) << " SCORES " << AA[i*100].score << " RATING =  " << gb << endl;
		}
 
 
        cerr << "anscnt = " << anscnt << " goodans = " << goodans << " badans = " << badans << " unique = " << unique << endl;
        REP(i, 10) cerr << "ANS[" << i << "]= " << anTM[i] << "/" << negTM[i] << endl;     
        cerr << "UTM0 = " << uniqueTM0 << " UTM1 = " << uniqueTM1 << " UTM2 = " << uniqueTM2 <<" UTM3 = " << uniqueTM3 <<" UTM4 = " << uniqueTM4 << " UTM5 = " << uniqueTM5 << " UTM6 = " << uniqueTM6 << " UTM7 = " << uniqueTM7 <<  endl;
 
    }
 
    ///----------------------------------------------------------------------------------------
 
    int init()
    {
 
        light = 0;
        frag_light = 0;
        R.clear();
        AA.clear();
        memset(P, 0, sizeof(P));
 
        gauss_init();
 
        #ifdef TRAIN
        train_init();
        #endif
 
        #ifdef DEBUG
        train_init();
        #endif
 
 
        return 0;
    }
 
 
    vector <string> getCraters()
    {
        sort_answers();
        REP(i, BB.size())
        {
			if (AA.size() < 95000) AA.PB(BB[i]); else break;
		}
        REP(i, CC.size())
        {
			if (AA.size() < 95000) AA.PB(CC[i]); else break;
		}        
 
        make_answers();
 
        #ifdef DEBUG
        calc_answers();
        sleep(1);
        #endif
 
        return R;
    }
 
 
    int processImage(string _name, int _W, int _H, vector <int> data)
    {
        W = _W; 
        H = _H;
        name = _name;
        make_array(data);
        make_edges();
 
        if (name[name.size()-3] == 't') czas = 170.0;
        else czas = 25.0;
 
        initTime();
 
        #ifdef DEBUG
        REP(i, answers.size())
        {
			if (answers[i].name == name) answers[i].used = 1;
		}
        #endif
 
        #ifdef TRAIN
        train(name);
        #endif
 
        #ifdef VISUAL
        present();
        sleep(1);
        #endif
 
        #ifdef NORMAL
        ZA = 0;
        bool start=0;
 
        REP(i, 8)
        {
            TM = i;
            algo1(name);
            if (i==4 && ZA < 500) start=1;
        }
 
        if (start && name[name.size()-3] == 't')
        {
			algo2(name, 90, 2.55, 20000);     
		} else
		if (ZA > 25000 && name[name.size()-3] == 't')
		{
			REP(i, AA.size())
			{
				if (AA[i].name == name)
				{
					AA[i].score += (int)3e7;
				}
			}
			algo2(name, 150, 6.0, 20000);
		} else
		if (ZA > 5000 && name[name.size()-3] == 't') 
        {
			algo2(name, 170, 5.0, 150);
		}	
 
		for(int y = 0; y <= H-21; y+= 20) for(int x = 0; x <= W-21; x+=20)
		{
			rectangle RC;
			RC.name = name;
			RC.miny = y;
			RC.minx = x;
			RC.maxy = y+20;
			RC.maxx = x+20;
			RC.score = (int)1e9;
			RC.probe = 9;
			RC.algo = 1;
			BB.PB(RC);
		} 
		for(int y = 10; y <= H-21; y+= 20) for(int x = 10; x <= W-21; x+=20)
		{
			rectangle RC;
			RC.name = name;
			RC.miny = y;
			RC.minx = x;
			RC.maxy = y+20;
			RC.maxx = x+20;
			RC.score = (int)1e9;
			RC.probe = 9;
			RC.algo = 1;
			BB.PB(RC);
		} 
		if (name[name.size()-3] == 't') for(int y = 0; y <= H-11; y+= 10) for(int x = 0; x <= W-11; x+=10)
		{
			rectangle RC;
			RC.name = name;
			RC.miny = y;
			RC.minx = x;
			RC.maxy = y+10;
			RC.maxx = x+10;
			RC.score = (int)1e9;
			RC.probe = 9;
			RC.algo = 1;
			CC.PB(RC);
		} 
		if (name[name.size()-3] == 't') for(int y = 5; y <= H-11; y+= 10) for(int x = 5; x <= W-11; x+=10)
		{
			rectangle RC;
			RC.name = name;
			RC.miny = y;
			RC.minx = x;
			RC.maxy = y+10;
			RC.maxx = x+10;
			RC.score = (int)1e9;
			RC.probe = 9;
			RC.algo = 1;
			CC.PB(RC);
		} 
		for(int y = 0; y <= H-31; y+= 30) for(int x = 0; x <= W-31; x+=30)
		{
			rectangle RC;
			RC.name = name;
			RC.miny = y;
			RC.minx = x;
			RC.maxy = y+30;
			RC.maxx = x+30;
			RC.score = (int)1e9;
			RC.probe = 9;
			RC.algo = 1;
			CC.PB(RC);
		} 
		for(int y = 0; y <= H-61; y+= 60) for(int x = 0; x <= W-61; x+=60)
		{
			rectangle RC;
			RC.name = name;
			RC.miny = y;
			RC.minx = x;
			RC.maxy = y+60;
			RC.maxx = x+60;
			RC.score = (int)1e9;
			RC.probe = 9;
			RC.algo = 1;
			CC.PB(RC);
		} 
		for(int y = 30; y <= H-61; y+= 60) for(int x = 30; x <= W-61; x+=60)
		{
			rectangle RC;
			RC.name = name;
			RC.miny = y;
			RC.minx = x;
			RC.maxy = y+60;
			RC.maxx = x+60;
			RC.score = (int)1e9;
			RC.probe = 9;
			RC.algo = 1;
			CC.PB(RC);
		} 
		for(int y = 10; y <= H-41; y+= 40) for(int x = 10; x <= W-41; x+=40)
		{
			rectangle RC;
			RC.name = name;
			RC.miny = y;
			RC.minx = x;
			RC.maxy = y+40;
			RC.maxx = x+40;
			RC.score = (int)1e9;
			RC.probe = 9;
			RC.algo = 1;
			BB.PB(RC);
		}		
		for(int y = 10; y <= H-81; y+= 80) for(int x = 10; x <= W-81; x+=80)
		{
			rectangle RC;
			RC.name = name;
			RC.miny = y;
			RC.minx = x;
			RC.maxy = y+80;
			RC.maxx = x+80;
			RC.score = (int)1e9;
			RC.probe = 9;
			RC.algo = 1;
			BB.PB(RC);
		}		
		for(int y = 40; y <= H-81; y+= 80) for(int x = 40; x <= W-81; x+=80)
		{
			rectangle RC;
			RC.name = name;
			RC.miny = y;
			RC.minx = x;
			RC.maxy = y+80;
			RC.maxx = x+80;
			RC.score = (int)1e9;
			RC.probe = 9;
			RC.algo = 1;
			BB.PB(RC);
		}		
 
		#endif
 
        return 0;
    }
 
 
 	///----------------------------------------------------------------------------------------------
 
    void gauss_init()
    {
		GxM[0][0] = -1; GxM[0][1] = 0; GxM[0][2] = 1;
		GxM[1][0] = -2; GxM[1][1] = 0; GxM[1][2] = 2;
		GxM[2][0] = -1; GxM[2][1] = 0; GxM[2][2] = 1;
 
		GyM[0][0] =  1; GyM[0][1] =  2; GyM[0][2] =  1;
		GyM[1][0] =  0; GyM[1][1] =  0; GyM[1][2] =  0;
		GyM[2][0] = -1; GyM[2][1] = -2; GyM[2][2] = -1;
 
		gM[0][0] = 2;	 gM[0][1] = 4;  gM[0][2] = 5;  gM[0][3] = 4;  gM[0][4] = 2;	
		gM[1][0] = 4;	 gM[1][1] = 9;  gM[1][2] = 12; gM[1][3] = 9;  gM[1][4] = 4;	
		gM[2][0] = 5;	 gM[2][1] = 12; gM[2][2] = 15; gM[2][3] = 12; gM[2][4] = 2;	
		gM[3][0] = 4;	 gM[3][1] = 9;  gM[3][2] = 12; gM[3][3] = 9;  gM[3][4] = 4;	
		gM[4][0] = 2;	 gM[4][1] = 4;  gM[4][2] = 5;  gM[4][3] = 4;  gM[4][4] = 2;			
	}
 
 
	void gaussian_blur()
    {
		memset(PE[UT], 0, sizeof(PE[UT]));
		FOR(y, 2, H-3) FOR(x, 2, W-3) 
		{
			int np = 0;
			FOR (yoff, -2, 2) FOR(xoff, -2, 2) 
			{
				np += P[y+yoff][x+xoff] * gM[2 + yoff][2 + xoff];
			}
			PE[UT][y][x] = np/159;
		}
	}	
 
 
    void sobel_mask()
    {
		FOR(y, 1, H-2) FOR(x, 1, W-2) 
		{
			double Gx = 0;
			double Gy = 0;
			FOR(yoff, -1, 1) FOR(xoff, -1, 1)
			{
				Gx += PE[UT][y+yoff][x+xoff] * GxM[xoff + 1][yoff + 1];
				Gy += PE[UT][y+yoff][x+xoff] * GyM[xoff + 1][yoff + 1];
			}
			double ta = (atan2(Gx,Gy)/3.14159) * 180.0;
			if (((ta > 112.5) && (ta < 157.5)) 	|| ((ta < -22.5) && (ta > -67.5))) 	eD[y][x] = 135;
			if (((ta > 67.5) && (ta < 112.5)) 	|| ((ta < -67.5) && (ta > -112.5)))	eD[y][x] = 90;
			if (((ta > 22.5) && (ta < 67.5)) 	|| ((ta < -112.5) && (ta > -157.5)))eD[y][x] = 45;
			if (((ta < 22.5) && (ta > -22.5)) 	|| (ta > 157.5) || (ta < -157.5)) 	eD[y][x] = 0;
			grd[y][x] = sqrt(pow(Gx,2.0) + pow(Gy,2.0));			
		}
	}
 
 
  	void trace_edges()
	{
		FOR(y, 1, H-2) FOR(x, 1, W-2) 
		{
			if (grd[y][x] > uTh) 
			{
				if (eD[y][x] == 0) 		find_e(0, 1, y, x, 0); 	else
				if (eD[y][x] == 45)		find_e(1, 1, y, x, 45);	else
				if (eD[y][x] == 90)		find_e(1, 0, y, x, 90);	else
				if (eD[y][x] == 135)	find_e(1, -1, y, x, 135);	else
				PE[UT][y][x] = 0;				
			}
			else PE[UT][y][x] = 0;
		}
		FOR(y, 0, H-1) FOR(x, 0, W-1) if (PE[UT][y][x] != 255) PE[UT][y][x] = 0;
	} 
 
 
 
    void find_e(int rs, int cs, int y, int x, int angle)
	{
		int _y;
		int _x;
		bool _end = 0;
 
		if (cs < 0) 
		{
			if (x > 0) _x = x + cs;
			else _end = 1;
		} else if (x < W - 1) _x = x + cs;
		else _end = 1;		
 
		if (rs < 0) 
		{
			if (y > 0) _y = y + rs;
			else _end = 1;
		} else if (y < H - 1) _y = y + rs;
		else _end = 1;	
 
		while ((grd[_y][_x] > lTh) && (eD[_y][_x]==angle) && !_end ) 
		{
			PE[UT][_y][_x] = 255;
			if (cs < 0) 
			{
				if (_x > 0) _x = _x + cs;
				else _end = 1;	
			} else if (_x < W - 1) _x = _x + cs;
			else _end = 1;
 
			if (rs < 0) 
			{
				if (_y > 0) _y = _y + rs;
				else _end = 1;
			} else if (_y < H - 1) _y = _y + rs;
			else _end = 1;	
		}	
	}
 
	void make_edges()
	{
		FOR(i, 1, 20)
		{
			if (i!=3 && i!=5 && i!=7 && i!=10) continue;
			UT = i;
			uTh = 10*i;
			lTh = 5*i;	
 
			gaussian_blur();
			sobel_mask();
			trace_edges();
		}
	}
 
    ///----------------------------------------------------------------------------------------
 
    void make_array(vector<int> data)
    {
        REP(i, H) REP(j, W) P[i][j] = data[H*j+i]; 
    }    
 
    void make_answers()
    {
        REP(i, AA.size())
        {
            stringstream ss;
            ss << AA[i].name << " " << AA[i].minx << " " << AA[i].miny << " " << AA[i].maxx  << " " << AA[i].maxy;
            //cerr << ss.str() << endl;
            R.PB(ss.str());            
        }
    }
 
    int diff_calc(int y, int x)
    {
        return abs(P[y][x] - lights[y/100][x/100]);
    }
 
    int diff_calc_e7(int y, int x) { return PE[7][y][x];}
 
    int frag_calc(int y, int x)
    {
        int fr = 0;
        if (x < W-1) fr = max(fr, abs(P[y][x+1] - P[y][x])); 
        if (x > 0) fr = max(fr, abs(P[y][x-1] - P[y][x])); 
        if (y < H-1) fr = max(fr, abs(P[y-1][x] - P[y][x])); 
        if (y > 0) fr = max(fr, abs(P[y+1][x] - P[y][x]));        
        return fr;
    }
 
    LD calc_best_circle(rectangle &RC)
    {
 
		int minr = min(RC.maxx-RC.minx, RC.maxy-RC.miny) * 0.5;
		int maxr = max(RC.maxx-RC.minx, RC.maxy-RC.miny);
 
		if (minr < 10) return -1.;
		if (maxr > 80) return -1.;
		if (RC.probe >= 1) return -1.;
		if (isTimeup()) return -1.; 
		if (name[name.size()-3] != 't') minr = max(15, minr); ///EDIT 1.8.5
		//cerr << "MR = " << minr << " XR = " << maxr << endl;
 
		LD ans = 0;
 
        FOR(km, minr, maxr)
        {
			double delta = 3;
			FOR(sy, RC.miny, RC.maxy-km-1)
			{
				//cerr << "HERE1" << endl;
				double cd, ci, ced, cei, fra, fri;
				cd = 0;
				ci = 0; 
				ced = 0;
				cei = 0;
				fra = 0;
				fri = 0;
 
				int cx = RC.minx + km/2;
				int cy = sy + km/2;
 
				int NYO[1500];
				int MYO[1500];
				int NYO2[1500];
				int MYO2[1500];
 
				/*
				REP(i, 1500) NYO[i] = -1;
				REP(i, 1500) MYO[i] = -1;
				REP(i, 1500) NYO2[i] = -1;
				REP(i, 1500) MYO2[i] = -1;
				*/
				memset(NYO, -1, sizeof(NYO));
				memset(MYO, -1, sizeof(NYO));
				memset(NYO2, -1, sizeof(NYO));
				memset(MYO2, -1, sizeof(NYO));
 
				FOR(y, sy, sy+km) FOR(x, RC.minx, RC.minx + km)
				{
					//cerr << "HERE2" << endl;
					int xdist = abs(x-cx);
					int ydist = abs(y-cy);
					double dist = sqrt ( pow((double)xdist, 2) + pow((double)ydist, 2) );
 
					if (dist > ((LD)km * (0.5)))
					{
						cd += diff_calc_e7(y, x);
						ci += 1;
					} else
					if (dist < ((LD)km*0.5 -delta))
					{
						ced += diff_calc_e7(y, x);
						cei += 1;
						if (NYO[y] == -1) NYO[y] = x;
						if (MYO[y] == -1) MYO[y] = x;
						NYO[y] = min(NYO[y], x);
						MYO[y] = max(MYO[y], x);                
					} else
					{
 
						fra+= diff_calc_e7(y, x);
						fri++;
 
						if (NYO2[y] == -1) NYO2[y] = x;
						if (MYO2[y] == -1) MYO2[y] = x;
						NYO2[y] = min(NYO2[y], x);
						MYO2[y] = max(MYO2[y], x);    
 
					}                
 
				}
 
				//cerr << ci << " " << cei << " " << fri << endl;
				//cerr << cd << " " << ced << " " << fra << endl;
				//FOR(i, 0, 50) cerr << NYO[i] << endl; 
				//FOR(i, 0, 50) cerr << MYO[i] << endl; 
				//FOR(i, 0, 50) cerr << NYO2[i] << endl; 
				//FOR(i, 0, 50) cerr << MYO2[i] << endl; 
 
				FOR(j, RC.minx, RC.maxx-km)
				{
					double ratio;
					if (fri > 0 && cei > 0  && fra > 0 && fri > 0) ratio = (fra/fri) / (ced/cei) ;
					else ratio = (fra==0 && ced > 0) ? 100 : 0;
					double frag = (fri==0)?0:fra/fri;
					//cerr << cd << " " << ci << " " << ced << " " << cei << endl;
					//if (cei > 0 && ci > 0 && fri > 0) cerr << "Y = " << sy << " X = " << j << " RATIO =  "  << ratio << " CENTERDIF = " << (ced/cei) << " CORNERDIFF = " << (cd/ci) << " FRAG = " << frag << endl;
					double cfrag = (cei==0)?0:ced/cei;
 
					ans = max (ans, (LD)(frag/255.));
					FOR(y, sy, sy+km) 
					{
						cd += diff_calc_e7(y,j+km+1);
						if (MYO2[y] != -1) 
						{
							cd -= diff_calc_e7(y, MYO2[y]);
							fra += diff_calc_e7(y, MYO2[y]);
						}
 
						if (MYO[y] != -1)
						{
							fra -= diff_calc_e7(y, MYO[y]);
							ced += diff_calc_e7(y, MYO[y]);
						}
 
						if (NYO[y] != -1)
						{
							ced -= diff_calc_e7(y, NYO[y]);
							fra += diff_calc_e7(y, NYO[y]);
						}
 
						if (NYO2[y] != -1)
						{
							fra -= diff_calc_e7(y, NYO2[y]);
							cd += diff_calc_e7(y, NYO2[y]);
						}
						cd -= diff_calc_e7(y,j);
 
						if (NYO[y] != -1) NYO[y]++; 
						if (MYO[y] != -1) MYO[y]++;
						if (NYO2[y] != -1) NYO2[y]++;
						if (MYO2[y] != -1) MYO2[y]++;
					}
				}
			}
		}		
		return ans;
	}    
 
    void calc_rectangle(rectangle &RC)
    {
		if (RC.algo==2) {calc_score(RC); return;}		
        double cd, ci, ced, cei, fra, fri, dil, dip, cf, cef, frd;
        cd = 0;
        cf = 0;
        ci = 0; 
        ced = 0;
        cef = 0;
        cei = 0;
        fra = 0;
        fri = 0;
        frd = 0;
        dil = 0;
        dip = 0;
 
        int cx = RC.minx + (RC.maxx-RC.minx)/2;
        int cy = RC.miny + (RC.maxy-RC.miny)/2;
 
        //kwadrat_size = RC.maxy - RC.miny;
 
        //RC.bestcirc = calc_best_circle(RC);
        LD crincir = 0;
        LD nocrincir = 0;
 
        FOR(y, RC.miny, RC.maxy) FOR(x, RC.minx, RC.maxx)
        {
            int xdist = abs(x-cx);
            int ydist = abs(y-cy);
            double dist = sqrt ( pow((double)xdist, 2) + pow((double)ydist, 2) );
 
            if (dist > kwadrat_size*0.50) continue;
 
			if (P[y][x] > lights[y/100][x/100]-35) nocrincir++;
			else crincir++;
		}
 
		RC.cratincircle = (crincir==0)?0:(crincir / (nocrincir+crincir));
 
        //cx-=2;
        RC.cx = cx;
        RC.cy = cy;
 
        FOR(y, RC.miny, RC.maxy) FOR(x, RC.minx, RC.maxx)
        {
            int xdist = abs(x-cx);
            int ydist = abs(y-cy);
            double dist = sqrt ( pow((double)xdist, 2) + pow((double)ydist, 2) );
 
            if (dist > ((LD)kwadrat_size * 0.5))
            {
                cd += abs(P[y][x] - lights[y/100][x/100]);
                cf += frag_calc(y,x);
                ci += 1;
            } else
            if (dist < ((LD)kwadrat_size * 0.3))
            {
                ced += abs(P[y][x] - lights[y/100][x/100]);
                cef += frag_calc(y,x);
                cei += 1;                
            } else
            {
 
                fra+=frag_calc(y,x);
                frd+=abs(P[y][x] - lights[y/100][x/100]);
                fri++;
            }            
 
            if (x <= cx) dil += P[y][x]; else dip += P[y][x];
        }        
 
        RC.sldp = (dip>0) ? dil/dip : 0;
 
        double ratio;
        double fragm = (fri>0) ? fra/fri : 0;
 
        if (cd > 0 && ci > 0 && cd/ci > 0 )
        {
            ratio = ((ced/cei)/(cd/ci));
        }
 
        RC.corndiff = (ci==0)? 0:(cd/ci);
        RC.cornfra = (ci==0) ? 0 : (cf/ci);
        RC.cenfra = (ci==0) ? 0 : (cef/cei);
        RC.cendiff = (cei==0)?0:(ced/cei);
        RC.frd = (fri==0)?0:(frd/fri);
        RC.ratio = ratio;
        RC.fraci = fragm;
        calc_score(RC);
    }
 
 
	/**
	 *  if (l.fraci > 10) scorel = 100;
        if (l.crater < 0.3) scorel += 100;
        if (l.ratio < 1.5) scorel *= 0.5;
        if (l.pole > 6000) scorel += 50; ///EDIT
        if (l.maxx-l.minx < 27 || l.maxy-l.miny < 27) scorel += 50;             
     */
 
    void calc_score(rectangle &l)
    { 
		if (l.algo == 2) {l.score = 200+l.ratio2; return;}  
        LD scorel = 100;
        if (l.frag < 50 && l.frag > 0) scorel = abs(5 - l.frag);
        else scorel = 1000000;
 
 
              //  if (l.differ > 30) scorel *= 0.5;
        if (l.maxx-l.minx < 25 || l.maxy-l.miny < 25) scorel+=2;
 
		if (l.sldp > 0.9) scorel += 1;
        if (l.sldp > 1.2) scorel += 50;  
        if (l.ultrablack < 0.15 && (l.ultrablack < (l.black/2))) scorel += 200; 
        if (l.rzp > 0.6) scorel+=1;        
		if (l.minx < 10 || l.miny < 10 || l.maxx > 590 || l.maxy > 390) scorel += 100;
        if (l.name[l.name.size()-3] == 't') 
        {
            scorel = abs(l.frag - 30);
            if (l.differ > 40) scorel *= 0.5;
            scorel += 100;
        }
 
        if (l.cratincircle < 0.9) scorel+=1;//100;
        if (l.cratincircle < 0.7) scorel+=100;//100;
        //if (l.bestcirc < 0.1 && l.bestcirc != -1) scorel+=10;
        if (l.cratincircle < 0.1) scorel+=10000000;//100;
 
        double ldx = l.maxx-l.minx;
        double ldy = l.maxy-l.miny;
 
        if (ldx > 1 && ldy > 1)
        {
            if ((max(ldx, ldy) / min(ldx, ldy)) > 1.2) scorel += 0.7; 
            if ((max(ldx, ldy) / min(ldx, ldy)) > 1.4) scorel += 100; 
        }
        if (l.name[l.name.size()-3] == 't' && l.black < 0.1) scorel+=10000;
        if ((l.frag < 0.1 || l.differ < 6) ) scorel += 10000;
        if (l.name[l.name.size()-3] != 't' && (l.maxx-l.minx < 16 || l.maxy-l.miny < 16)) scorel += 100000;                
        if (max(l.maxx-l.minx, l.maxy-l.miny) > 260) scorel += 100000;                
        scorel += l.probe * 1000000;
        if (l.maxx-l.minx < 10 || l.maxy-l.miny < 10) scorel += 10000000;                
        if (max(l.maxx-l.minx, l.maxy-l.miny) > 350) scorel += 10000000;                
        l.score = scorel;
        ZA++;
    }
 
    void sort_answers()
    {   
		//int num = 0;
		//REP(i, AA.size()) if (AA[i].probe == 0 && AA[i].name[AA[i].name.size()-3] == 't') num++;
        //cerr << num << endl;
        //REP(i, AA.size()) calc_score(AA[i]);
        sort(ALL(AA), crc);
    }
 
 
	///----------------------------------------------------------------------------------------------
 
 
    int minx, miny, maxx, maxy;
    int xx, xy, nx, ny;
    int cratile;
    int blackile;
    int ultrablack;
    int frag;
    int differ;
    int rzp;
    vector<int> fragmenty;
    int aktualny_fragment;
 
    void add_rect()
    {
        if (xx<(W-(10)-1)) xx+= 10;  
 
        int pole = (xx-nx)*(xy-ny); if (pole==0) return;
 
        rectangle A;
        A.probe = TM;
        A.pole = pole;
        A.black = (LD)blackile/pole;
        A.crater = (LD)cratile/pole;
        A.frag = (LD)frag/pole;
        A.ultrablack = (LD)ultrablack/pole;
        A.differ = (LD)differ/pole;
        A.rzp = (LD)rzp/cratile;
        A.minx = nx;
        A.miny = ny;
        A.maxx = xx;
        A.maxy = xy;
        A.name = name;
        A.md = 0;
        A.uniq = 0;        
        A.algo = 1;
        A.fragmenty = fragmenty;
        calc_rectangle(A);
        if (AA.size() > 90000) return;
        int six = xx-nx;
        int siy = xy-ny;
 
        if (six==0 || siy==0 || (max(six, siy) / min(six, siy)) > 5) return;
 
        AA.PB(A);		
	}
 
	void dfs2_clear_global(int y, int x)
	{
		fragmenty.clear();
		aktualny_fragment = 0;
        xx = x;
        nx = x;
        ny = y;
        xy = y;
        cratile = 0;
        blackile = 0;
        ultrablack = 0;
        frag=0;
        differ=0;
        rzp=0;		
	}
 
    void start_dfs2(int y, int x)
    {
		if(name[name.size()-3] == 't')
		{
			FOR(i, -10, 10) FOR(j, -10, 10) 
			{
				if (x+j<0 || y+i<0 || x+j>W-1 || y+i>H-1 || crat[y+i][x+j]) continue;
				dfs2_clear_global(y, x);
				//if (aktualny_fragment != 0) fragmenty.PB(aktualny_fragment);
				//aktualny_fragment=0;
				dfs2(y+i,x+j);
				if (aktualny_fragment > 50 || TM!=0) {aktualny_fragment = 0; add_rect();}
			}
		}else
		{
			dfs2_clear_global(y, x);
			FOR(i, -10, 10) FOR(j, -10, 10) 
			{
				if (x+j<0 || y+i<0 || x+j>W-1 || y+i>H-1 || crat[y+i][x+j]) continue;
				if (aktualny_fragment != 0) fragmenty.PB(aktualny_fragment);
				aktualny_fragment=0;
				dfs2(y+i,x+j);
			}
			if (aktualny_fragment != 0) fragmenty.PB(aktualny_fragment);
			if (cratile > 150) add_rect(); 
 
		}
		//if (aktualny_fragment != 0) fragmenty.PB(aktualny_fragment);
    }
 
    bool dfs2(int y, int x)
    {
        if (x<0 || y<0 || x>W-1 || y>H-1 || crat[y][x]) return 0;
        crat[y][x]=1;
 
        if (TM == 0) if (P[y][x] > lights[y/100][x/100]-35) return 0;     
        if (TM == 1) if (P[y][x] > lights[y/100][x/100]-55) return 0;    
        if (TM == 2) if (P[y][x] > lights[y/100][x/100]-25) return 0; 
        if (TM == 3) if (P[y][x] > lights[y/100][x/100]-45) return 0; 
        if (TM == 4) if (P[y][x] > lights[y/100][x/100]-15) return 0; 
        if (TM == 5) if (P[y][x] > lights[y/100][x/100]-65) return 0; 
        if (TM == 6) if (P[y][x] > lights[y/100][x/100]-5) return 0; 
        if (TM == 7) if (P[y][x] > lights[y/100][x/100]-75) return 0; 
        if (TM > 7)  if (P[y][x] > lights[y/100][x/100]-35) return 0;    
 
        if (P[y][x] <= max(20, lights[y/100][x/100]-40)) blackile++; 
        if (P[y][x] <= max(10, lights[y/100][x/100]-60)) ultrablack++;
 
 
        frag+=frag_calc(y, x);
        if (frag_calc(y,x) > 10) rzp++;
        differ += abs(P[y][x] - lights[y/100][x/100]);
        cratile++;
        aktualny_fragment++;
 
        xx = max(xx,x);
        xy = max(xy,y);
        nx = min(nx,x);
        ny = min(ny,y);
 
 
        dfs2(y-1,x);
        dfs2(y+1,x);
        dfs2(y,x-1);
        dfs2(y,x+1);
 
        return 1;
 
    }
 
    void start_dfs(string name, int y, int x)
    {
        minx = x;
        miny = y;
 
        maxx=0;
        maxy=0;
 
        dfs(y,x);
 
        miny*=kwadrat_size;
        minx*=kwadrat_size;
        maxy*=kwadrat_size;
        maxx*=kwadrat_size;
 
        minx = max(0, minx);
        miny = max(0, miny);
        maxy = min(H-1, maxy);
        maxx = min(W-1, maxx);
 
        int cx = (minx+maxx)/2;
        int cy = (miny+maxy)/2;
 
        start_dfs2(cy, cx);
 
    }
 
    void dfs(int y, int x)
    {
        if (!used[y][x]) return;
        minx = min(minx, x);
        miny = min(miny, y);
        maxx = max(maxx, x);
        maxy = max(maxy, y);
        used[y][x]=0;
        if (x!=W/kwadrat_size-1 && used[y][x+1]) dfs(y, x+1);
        if (y!=H/kwadrat_size-1 && used[y+1][x]) dfs(y+1, x);
        if (x!=0 && used[y][x-1]) dfs(y, x-1);
        if (y!=0 && used[y-1][x]) dfs(y-1, x);
    }
 
    ///Speed Hough transform
 
    void algo1(string name)
    {
        kwadrat_size = 13;//13;
        if (name[name.size()-3] == 't') kwadrat_size = 8;
        if (TM%7 == 1) kwadrat_size = 7;
        if (TM%7 == 2) kwadrat_size = 4;
        if (TM%7 == 3) kwadrat_size = 2;
        kwadrat_sum = kwadrat_size*kwadrat_size*15;//*ZI;
        if (TM%7 == 4) kwadrat_sum = kwadrat_size*kwadrat_size*25;//*ZI;
        if (TM%7 == 5) kwadrat_sum = kwadrat_size*kwadrat_size*5;//*Z;
        if (TM%7 == 6)
        {
            kwadrat_size = 20;
            kwadrat_sum = kwadrat_size*kwadrat_size*30;
        }
 
        //kwadrat_sums = kwadrat_size*kwadrat_size*190;//*ZI;
 
        check_light();        
        memset(used, 0, sizeof(used));
        memset(crat, 0, sizeof(crat));
 
        int kwadrat;
 
        FOR(i, 0, H-kwadrat_size-1) 
        {
            kwadrat = 0;
            FOR(y, i, i+kwadrat_size-1) FOR(x, 0, kwadrat_size-1) kwadrat += P[y][x];
            FOR(j, 0, W-kwadrat_size-1)
            {
                FOR(y, i, i+kwadrat_size-1) kwadrat -= P[y][j];
                FOR(y, i, i+kwadrat_size-1) kwadrat += P[y][j+kwadrat_size];
                if (kwadrat < kwadrat_sum && !used[i/kwadrat_size][j/kwadrat_size])
                {
                    used[i/kwadrat_size][j/kwadrat_size]=1;
                }
            }
        }
 
        int k = 0;
        REP(i, H/kwadrat_size-1) REP(j, W/kwadrat_size-1) if (used[i][j] == 1) {start_dfs(name, i, j);}        
    }
 
 
    void check_light()
    {
        LL l_sum = 0;
        memset(lights, 0, sizeof(lights));
        FOR(i, 0, H-1)
        {
            FOR(j, 0, W-1)
            {
                l_sum += P[i][j];
                lights[i/100][j/100] += P[i][j];
            }
        }
        ///TODO: 43 ends
        REP(i, 20) REP(j, 20) lights[i][j]/=10000;
 
        light = l_sum / (W*H);
        //cerr << light << endl;
        kwadrat_sum = kwadrat_size * kwadrat_size * (light*0.2);
        //cerr << "LIGHT: " << light << endl; 
    }
 
    ///Speed Hough transform
 
    void algo2(string name, double gran, double _ratio, int maxnum)
    {       
 
        int inum, obro;
        inum = 0;
        obro = 0;
        bool chosen[1500][1500];
        memset(chosen, 0, sizeof(chosen));
 
        FORD(km, 34, 10)
        //FORD(km, 25, 25)
        {
			obro = 0;
			//double delta = 0.15;
			double delta = 3;
			//if (km < 20) delta = 0.06;
			//cerr << "----" << km << "----" << endl;
			FOR(sy, 0, 1300)
			//FOR(sy, 182, 182)
			{
				//if (sy%200 == 0) cerr << "*" << endl;
				//if (inum > 1000 || (sy%100==0 && isTimeup())) break;
				if (inum > maxnum || (sy%100==0 && isTimeup())) break;
				kwadrat_size = km;
				double cd, ci, ced, cei, fra, fri;
				cd = 0;
				ci = 0; 
				ced = 0;
				cei = 0;
				fra = 0;
				fri = 0;
 
 
 
				int cx = kwadrat_size/2;
				int cy = sy + kwadrat_size/2;
 
				int NYO[1500];
				int MYO[1500];
				int NYO2[1500];
				int MYO2[1500];
 
				REP(i, 1500) NYO[i] = -1;
				REP(i, 1500) MYO[i] = -1;
				REP(i, 1500) NYO2[i] = -1;
				REP(i, 1500) MYO2[i] = -1;
 
				FOR(y, sy, sy+kwadrat_size) FOR(x, 0, kwadrat_size)
				{
					int xdist = abs(x-cx);
					int ydist = abs(y-cy);
					double dist = sqrt ( pow((double)xdist, 2) + pow((double)ydist, 2) );
 
					if (dist > ((LD)kwadrat_size * (0.5)))
					{
						cd += diff_calc_e7(y, x);
						ci += 1;
					} else
					if (dist < ((LD)kwadrat_size*0.5 -delta))
					{
						ced += diff_calc_e7(y, x);
						cei += 1;
						if (NYO[y] == -1) NYO[y] = x;
						if (MYO[y] == -1) MYO[y] = x;
						NYO[y] = min(NYO[y], x);
						MYO[y] = max(MYO[y], x);                
					} else
					{
 
						fra+= diff_calc_e7(y, x);
						fri++;
 
						if (NYO2[y] == -1) NYO2[y] = x;
						if (MYO2[y] == -1) MYO2[y] = x;
						NYO2[y] = min(NYO2[y], x);
						MYO2[y] = max(MYO2[y], x);    
 
					}                
 
				}
 
				FOR(j, 0, W-kwadrat_size-2)
				{
					double ratio;
					if (fri > 0 && cei > 0  && fra > 0 && fri > 0) ratio = (fra/fri) / (ced/cei) ;
					else ratio = (fra==0 && ced > 0) ? 100 : 0;
					double frag = (fri==0)?0:fra/fri;
					double cfrag = (cei==0)?0:ced/cei;
 
					if (ratio > _ratio && frag > gran &&  sy > 20 && ((km > 15 || ratio > 1.5*_ratio)))
					{
 
						rectangle R;
						R.minx = j;
						R.maxx = j+kwadrat_size;
						R.miny = sy;
						R.maxy = sy+kwadrat_size;
						R.name = name;
						R.ratio2 = inum;
						R.probe = 0;
				        R.md = 0;
						R.uniq = 0; 
						R.algo = 2;
 
						bool ok = 1;
 
						FOR(yy, R.miny, R.maxy) 
						{
							FOR(xx, R.minx, R.maxx) if (chosen[yy][xx]) ok = 0;
							if (ok==0) break;
						}
 
						if (ok)
						{
							inum++;
							FOR(yy, R.miny, R.maxy) FOR(xx, R.minx, R.maxx) chosen[yy][xx] = 1;
							calc_rectangle(R);
							AA.PB(R);
						}
					}
					FOR(y, sy, sy+kwadrat_size) 
					{
						cd += diff_calc_e7(y,j+kwadrat_size+1);
						if (MYO2[y] != -1) 
						{
							cd -= diff_calc_e7(y, MYO2[y]);
							fra += diff_calc_e7(y, MYO2[y]);
						}
 
						if (MYO[y] != -1)
						{
							fra -= diff_calc_e7(y, MYO[y]);
							ced += diff_calc_e7(y, MYO[y]);
						}
 
						if (NYO[y] != -1)
						{
							ced -= diff_calc_e7(y, NYO[y]);
							fra += diff_calc_e7(y, NYO[y]);
						}
 
						if (NYO2[y] != -1)
						{
							fra -= diff_calc_e7(y, NYO2[y]);
							cd += diff_calc_e7(y, NYO2[y]);
						}
						cd -= diff_calc_e7(y,j);
 
						if (NYO[y] != -1) NYO[y]++; 
						if (MYO[y] != -1) MYO[y]++;
						if (NYO2[y] != -1) NYO2[y]++;
						if (MYO2[y] != -1) MYO2[y]++;
					}
				}
			}
		}
		sleep(1);
    }   
 
 
 
 
    void present()
    {
		check_light();
        FOR(i, 34, 71)
        {
            FOR(j, 205, 246)
            {
                //if ( abs(P[i][j] - P[i][j-1]) > 30) cerr << " R "; else
                //if ( abs(P[i][j] - P[i][j+1]) > 30) cerr << " R "; else
                //if ( abs(P[i][j] - P[i-1][j]) > 30) cerr << " R "; else
                //if ( abs(P[i][j] - P[i+1][j]) > 30) cerr << " R "; else
                //cerr << " * "; 
                cerr << P[i][j]-lights[i/100][j/100];
                if (P[i][j]-lights[i/100][j/100] <= -100) cerr << ""; else
                if (P[i][j]-lights[i/100][j/100] <= -10) cerr << " "; else
                if (P[i][j]-lights[i/100][j/100] <= -1) cerr << "  "; else
                if (P[i][j]-lights[i/100][j/100] <= 9) cerr << "   "; else
                if (P[i][j]-lights[i/100][j/100] <= 99) cerr << "  "; else
                cerr << " ";
            }
            cerr << endl;
        }        
    }
 
    void train_read_answers()
    {
        ///Read answers
        fstream fs("GTF.lms", ios::in);
        //fstream fs("training/LRO/GTF.lms", ios::in);
        //fstream fs("training/A15/GTF.lms", ios::in);
 
        string str;
        string _name;
        while(fs >> _name)
        {
            answer A;
            A.name = _name;
            A.used = 0;
            int num;
            string foo;
            fs >> foo;
            fs >> num;
            fs >> foo;
            REP(i, num) 
            {
                int minx,miny,maxx,maxy;
                fs >> minx >> foo >> miny >> foo >> maxx >> foo >> maxy >> foo;
                rectangle R;
                R.minx = minx;
                R.miny = miny;
                R.maxx = maxx;
                R.maxy = maxy;
                R.md = 0;
                A.rectangles.PB(R);
            }
            answers.PB(A);
        }
 
    }
 
    void train_init()
    {
        train_read_answers();
    }
 
    void train(string name)
    {
        int tid = -1;
        int found = 0;
        check_light();
        REP(i, answers.size()) if (name == answers[i].name) tid = i;     
        //cerr << "ANS = " << answers[tid].rectangles.size() << endl;
 
        int n = answers[tid].rectangles.size();
 
        REP(i, H) REP(j, W) crat[i][j]=0;
 
        REP(z, n)
        {
            int kwadrat;
            bool can_found = 0;
            int minx = answers[tid].rectangles[z].minx;
            int miny = answers[tid].rectangles[z].miny;
            int maxx = answers[tid].rectangles[z].maxx;
            int maxy = answers[tid].rectangles[z].maxy;
            FOR(i, miny, maxy-kwadrat_size-1) 
            {
                kwadrat = 0;
                FOR(y, i, i+kwadrat_size-1) FOR(x, minx, kwadrat_size-1) kwadrat += P[y][x];
                FOR(j, minx, maxx-kwadrat_size-1)
                {
                    FOR(y, i, i+kwadrat_size-1) kwadrat -= P[y][j];
                    FOR(y, i, i+kwadrat_size-1) kwadrat += P[y][j+kwadrat_size];
                    if (kwadrat < kwadrat_sum)
                    {
                        can_found = 1;
                    }
                }
            }
            //if (!can_found) cerr << "NAME: " << name << " MINX: " << minx << " MINY: " << miny << endl;
 
            int cx = (minx+maxx)/2;
            int cy = (miny+maxy)/2;
            //start_dfs2(cy,cx);
 
            frag=differ=cratile=blackile=ultrablack;
 
            FOR(i, miny, maxy) FOR(j, minx, maxx) 
            {
                differ += abs(P[i][j] - lights[i/100][j/100]);
                int fr = 0;
                fr = max(fr, abs(P[i][j+1] - P[i][j])); 
                fr = max(fr, abs(P[i][j-1] - P[i][j])); 
                fr = max(fr, abs(P[i-1][j] - P[i][j])); 
                fr = max(fr, abs(P[i+1][j] - P[i][j])); 
                frag+=fr;
            }
 
            int pole  = (maxx-minx) * (maxy-miny);
            if (pole == 0) return;
            LD cr = (LD)cratile/pole;
            LD bc = (LD)blackile/pole;
            LD ub = (LD)ultrablack/pole;
            LD frg = (LD)frag/pole;
            LD di = (LD)differ/pole;
 
            cerr << "POLE = " << pole << " CR = " << cr << " BC = " << bc << " UB = " << ub << " FRG = " << frg << " DI = " << di << endl;
            cerr << "    MINX: " << minx << " MINY: " << miny << " MAXX: " << maxx << " MAXY: " << maxy << endl;
            cerr << "MY " << " MINX: " << nx << " MINY: " << ny << " MAXX: " << xx << " MAXY: " << xy << endl;
 
 
            rectangle A;
            A.pole = pole;
            A.black = (LD)blackile/pole;
            A.crater = (LD)cratile/pole;
            A.frag = (LD)frag/pole;
            A.ultrablack = (LD)ultrablack/pole;
            A.minx = nx;
            A.miny = ny;
            A.maxx = xx;
            A.maxy = xy;
            A.name = name;
 
            AA.PB(A);
 
        }
 
 
    }
 
 
};