| ||||
|
На главную
.............. Задачи .............. Финальная статистика .............. Общая статистика .............. Правила .............. 
|
#include <iostream>
#include <math.h>
#include <assert.h>
#ifndef ONLINE_JUDGE
#include <io.h>
#endif
using namespace std;
typedef unsigned char U8;
typedef unsigned int U32;
typedef unsigned long long U64;
typedef signed char I8;
typedef signed int I32;
typedef signed long long I64;
#define countof(x) (sizeof(x)/sizeof(*(x)))
enum {NI=36,NH=20,NO=26};
const double wi[NI][NH]={
{1.38690838948,2.29982374068,-4.27623276436,1.83849029447,-1.05521540336,-4.16232619309,1.86788325806,-1.87307985457,-0.716933732221,-1.3113184004,1.86160741886,0.422296439847,1.22391823255,2.94577856473,2.6565738692,-1.78753586318,0.442725585721,4.41984926393,1.08143224777,2.42956743371},
{0.000638629456322,0.726358870474,-0.88770194277,-0.172324451829,-0.552308549192,-0.639135361726,-2.23801654681,1.87997942806,0.664534777411,1.56802859199,0.0677034676444,0.570940697748,-0.854917778037,-0.614197842122,1.28862562825,-0.177294773683,-0.462978475609,-0.618416739934,-3.88913547291,0.2624779979},
{-0.936451913455,1.63168500646,1.70384683703,0.263595998002,-1.93540310954,5.90906433536,-1.85353073142,1.98448432704,0.440410722424,3.77849927228,1.39167861614,1.20833162569,-1.15130593032,-1.94830986568,2.13141529774,1.53647955805,-2.05296531189,-0.169108088509,0.343297649306,-1.61833967957},
{0.956685520948,-1.06221115171,0.218662810443,-0.456478617747,2.26178468815,3.2686622398,-0.173837958238,-0.89719875715,-1.33685510533,-0.444080679013,-0.903668703761,0.516787339909,3.05715473201,1.1417682416,-0.848795920874,-2.59986330521,3.11354848638,0.751197514754,0.429456068306,0.720310250604},
{-1.50309005236,-3.99102126034,-1.52617606567,-1.94071532512,-0.380005237927,-1.01042869044,2.9704171217,-1.95668684244,3.14660246306,0.577855709382,1.80467565497,-0.356037385081,1.29676078968,2.47080904148,2.47575585584,0.164868792149,3.27405071665,-4.87540366442,5.48387873663,-0.118937542757},
{-0.64978044913,-0.603507536731,-1.57801287883,-0.481998808641,-2.1870540328,-1.39934942292,0.0624454112458,-0.979938738213,0.990928735652,-1.54016272193,-0.929676839051,-0.599491327772,-1.73235363127,0.51710412876,2.98184821396,-1.56845730298,-0.28437069768,0.31241289,0.878759042525,1.08993169687},
{-0.987730889468,2.29820351584,-3.53656687141,-2.11498510144,1.33804317548,-0.264592786131,-0.525468133078,-2.28816898293,-1.3825445153,-1.37356317579,1.26455904864,1.26741551566,-1.05196182521,0.920643162296,0.795857839321,1.88839030708,-1.2088183737,0.106727266833,-1.07957527297,-3.95820767517},
{-0.375244729729,-0.053450701324,1.01038590107,2.33061759914,-2.74199268991,0.155277393964,1.70214900705,0.168094296405,2.41302989114,3.77436556321,1.00280292873,2.76034547311,-1.66403015581,1.61274779725,2.55695924166,-3.14433200685,-1.27213612818,0.514201629786,0.498959276405,1.47125094377},
{3.09294931806,-1.08701026335,0.694822273621,-1.68811414872,1.27687403673,1.16487205795,0.502340923701,-2.50229228519,0.351185163821,-2.16392683822,1.17450510815,-3.24535181851,1.58593175812,-1.97599338455,0.735049912934,-0.0165490280613,0.0448536270484,3.45569967959,0.576461241599,2.66590762271},
{0.360787051102,-1.54323168854,-1.10519600984,2.02307687746,0.00494857204214,4.43107264205,-2.58542784769,-2.09907635564,0.295471632693,-1.18054495635,0.67428153761,-0.13946234396,1.03856534447,-0.271975982788,1.57358356426,-1.48745366915,3.89169210966,0.471822742069,0.89607737057,-2.08733324284},
{-0.852282471603,-3.30830079576,-1.94987685352,-1.61827079271,0.119642931302,-0.466557935949,-0.327003501007,3.73440803165,-0.480333925652,-0.691131375272,0.428561769191,0.519439796471,0.368752479023,1.37920954537,-1.86899848611,1.25833619536,0.57111916744,-2.58242143147,-1.2129181276,0.825013074749},
{-3.20387217792,-0.660262581214,-4.552415864,1.26379426623,-1.73752213549,-3.17139165988,-0.762354320259,0.758535869201,-1.22936334628,-2.19852443165,0.888481556887,2.57273781076,-0.281290324224,3.27059646709,-0.52954676471,2.34332384918,1.42483869453,1.05774004618,-1.10579102753,-3.90330990688},
{-0.173481935381,1.24691381604,1.5444826506,-0.780509712453,-3.9473131857,-0.205090934532,3.20430598332,-2.42117114007,-1.53115144058,0.153704318077,0.896159959678,3.10440681525,1.06386338391,1.43691357967,0.252217671131,-2.37618238108,-0.150206624566,1.70505516305,2.6866617249,1.8097573213},
{1.19555470095,2.40947674641,-0.0863171800682,-1.50798062495,1.30297216613,0.471100082091,-1.72137534955,-4.23188337043,-0.628463610396,-0.684439717714,0.894065375329,1.11863004022,4.9950988466,-3.63127749473,-2.68891250026,2.75336429845,-1.49518476387,0.0759404167596,2.81641503269,-0.204908208202},
{5.66918646744,2.95934969006,-1.00610231669,3.34873065515,2.12222039613,-1.86121043961,-4.10529001412,-2.20232631062,-2.17126624475,-1.8524744489,1.72489814121,2.18356397244,2.04637781128,-2.62703934854,1.42877336469,-0.75220333552,1.38746655833,0.470089025932,-4.68187959885,1.46810805698},
{1.75231224819,2.78491765996,0.105134510987,-5.15139278908,2.50509778633,-0.611996428676,-2.48102037609,0.829664777155,-0.0632183712313,-2.60296583753,-1.41080226521,0.535173854629,-0.0892423153162,-0.391695081631,1.31528353432,0.366581895812,0.967789920122,-1.14362827749,-0.227210373128,2.46993874015},
{-1.63861189837,1.78067350095,-5.33715950496,1.34894407886,-2.46215708989,3.15237659023,-1.70607149486,5.16843772976,-1.01552372033,0.428438232796,-0.850655443607,1.98451894861,-2.955286229,-1.4518207929,-2.09749481966,-1.08141574307,4.64346625033,-0.91056828801,1.94294733405,-0.75609000274},
{-0.551120343065,-0.686595861086,0.598222199951,-0.411162274908,-0.887518461945,3.12137118949,4.2510220145,-0.529925916428,-0.268742859958,-0.808912317719,-0.0322084162292,5.65635062288,0.192014505549,-4.39898867389,-0.832219800665,-0.344668595175,-1.08223888936,3.53907905933,3.27521646616,0.705735082513},
{-1.18559225574,-2.24813153956,-0.407601316286,5.60336091589,0.611309377385,1.71187251584,2.9311233192,6.26345069837,-3.10289737441,-0.0563559201626,1.56147584077,2.15817297668,-0.505166079094,-1.3839151845,-5.53436798036,2.26369146706,2.23941944634,-3.73122203671,-1.08677456342,2.57850041433},
{0.541728474324,3.43527184069,4.86495636269,2.85343081684,0.403132190317,-1.53689004818,0.928820274932,-3.10771223503,2.39331044422,1.32941719241,1.69600154969,-0.424959024125,-0.553035269567,-2.90322076561,-0.258435889393,0.0555299209843,1.40863380785,-0.850085853618,-0.152007102713,5.03940825219},
{0.740495634993,1.94175564264,-1.88156092842,-1.03322737958,-0.0492061128508,0.024633662997,-1.58536558646,2.37445194893,2.19727578665,-1.31302948979,0.119603714613,1.25420650824,-3.31323458814,0.0615815943187,0.279567966961,-0.736338709427,1.65191401953,-2.06277571238,-1.38634010887,-1.74477973011},
{0.142454070407,3.14910027307,5.61645465823,0.362655180046,-2.40898855683,-0.00720316630572,-0.39047483597,-1.11327048495,0.744068131724,-1.23513817143,0.275786005354,-2.51903700442,-1.54260304007,0.921706658028,2.82353897904,-1.18530765305,-1.83798893743,-2.11719923811,0.466703470026,3.62103366153},
{2.19283129641,0.913810308831,1.65119457039,0.588778180478,-0.326456927,-1.42960077114,-2.073449032,0.707626544933,0.223099271159,2.62887592163,-1.0666704911,0.812008171873,2.16704988269,-0.291245220839,1.87776005115,0.327995918248,1.95196198168,-0.557907928796,0.60792497436,-4.1635481006},
{-0.433093047822,-3.0086991712,5.20638151881,3.84798620006,2.81107711636,-3.96286708115,0.0928895216648,1.35672474928,0.613603918915,3.40460498232,2.01712466157,-0.199715955502,-2.33160153008,0.732631446878,-1.09904509944,0.616188631273,0.667600672423,-0.341778179146,0.84491157929,-0.331557263722},
{-7.38160897769,0.374440798132,1.23355346161,2.02816260082,-1.18326071714,-0.545037267804,1.5362338389,-1.64696320239,4.29813654259,1.5890392042,-1.81907767662,-0.720570421497,0.219237164284,-0.890097810366,-2.72803920031,2.24584866014,2.32675956131,0.165526903259,-3.30242780011,1.5405014386},
{-1.00302120152,-0.968616417145,1.31506160465,3.29133304158,-0.663826210963,1.29008585459,2.1444973917,-1.67688998992,-0.417409068937,0.951165138151,2.16523437982,-2.68869999008,-3.47771588152,-0.928207756433,-1.23087809308,2.84454185848,-0.955912136343,0.115997618159,-1.930752595,-5.09343137644},
{2.51162953474,-2.82056553681,2.23861699866,-4.67413449831,1.0747456533,-1.5368057962,2.92325518453,1.26319084614,-0.92059078173,-0.676126199314,2.1167607883,-1.27893251078,0.239180879149,-0.329138610991,1.9160665354,0.351095887091,-1.15142331581,-2.70019189292,-1.59001850415,2.09024823369},
{1.84858644721,-0.765249205753,-2.10947173342,-0.357844498986,-2.21906488758,-4.06761256589,-3.39298478597,3.02137924567,-1.88479653285,0.346105991177,-1.04875722722,-2.10758919816,4.44231234864,-2.59449966849,1.0035352694,1.23537776222,0.435667185832,-0.777014235238,0.747872555228,-3.61199301733},
{-0.978979628541,-1.94979832947,-0.841295612852,0.630411815153,2.63975640838,-0.187145440189,1.31641506335,-2.15441074094,-0.225916552709,-0.305398193045,1.58317335216,-0.516423671619,-3.02003121258,2.40931772237,1.6197497155,-3.88709311749,-0.88190402502,2.70671245073,0.283240166572,-0.55173037266},
{-0.295711390373,0.270471450706,-1.94438663792,-1.57440450495,1.76592923489,1.38630285091,-0.772792799717,2.3155599425,2.36800029165,0.298253516266,0.346726860182,-2.10544322429,1.70388407412,4.03572674762,-6.37018159086,1.58163919358,-2.02306713603,2.58304599938,-0.283006691645,0.625718871582},
{-2.56932998394,4.63929573729,-0.395406281506,3.33864600009,-1.73451986153,-0.792586933568,0.201412816722,-0.332281666256,-1.10597211042,-2.32617362682,1.34627376284,2.15700835904,-2.31803406009,-0.497781439073,-0.153646694563,1.92262735326,-3.1225469326,2.16962389691,0.234485936043,-0.193690172574},
{-0.116122530256,-0.288935524027,-0.732028889449,1.04896871728,0.840480287037,-0.496000589808,0.472376449032,-1.051072011,-0.138357407149,-0.720150057698,1.06021703727,2.20440509974,-1.54462137318,-0.73685610312,-0.571875804966,0.323565212335,0.982329970276,-1.19143969592,-0.933842418553,-1.07871429244},
{1.35489174275,0.093876586971,0.222656050242,-1.97147699283,-1.95039068949,1.89956504522,2.22418662261,-1.25318544866,-0.98137969962,1.17470407649,0.896240108229,-4.5986184667,2.47254402258,0.663356147997,-0.361865093978,2.99321768928,0.228509704772,1.54199652625,-3.67596222732,-0.979744988907},
{0.734382329557,-0.0804800670624,2.67134196457,-3.84632972419,-1.84944671347,-1.82959055928,2.88087101798,2.35376187124,2.31930398072,-0.228547455056,-0.721964914864,-1.31200105014,-0.323802126118,-0.684743459426,-3.01923869821,-0.760796439477,-1.25510880951,1.03496158953,-0.566742714949,2.71029347229},
{3.78452934899,1.48167040375,2.95727147574,-5.35815186503,3.43994060025,-4.07682809005,2.93164612204,5.4437442232,2.5166197386,-2.48779548466,-0.723957919142,-1.67761937266,2.55866382779,0.822582917305,-3.85530777014,-1.75093944587,-2.24196314652,1.05061991586,2.93899060837,-2.58332647842},
{0.167141910868,-1.77671463089,0.07177137688,0.14019450073,1.24386725839,-0.311553243046,-1.29512753374,-1.1591019554,0.911569008597,-0.252877896871,1.10245952191,-1.85861114208,0.122456701555,1.1657927326,1.92488728351,1.67505558234,-0.529440014016,-2.2015000458,1.70989380082,-1.44372234978}
};
const double wo[NH][NO]={
{-5.02001171833,-6.46872741435,0.638432666215,-3.20773828987,0.882738270652,-10.5434972992,-3.65018327962,-4.5807405651,-2.43899250068,0.833571056809,-0.412280833541,-0.397678708638,1.91610439614,-5.08195549454,2.2110425862,4.45886752507,-0.752444334493,3.56222876256,-5.29007911837,-1.50641837533,-1.36834345685,-1.11595635658,-0.790863494186,1.30165456771,-1.87560357458,-1.31439530063},
{0.626552228885,6.11505130001,-4.99327324338,2.23898714741,1.39509177851,-0.433162563639,-5.35332607318,-2.802105105,2.31477685802,-6.28758790146,-1.24839698315,3.54116171968,2.59356612729,-0.323116349318,2.97014390315,1.99953763781,-1.9763977169,1.23250825026,-11.1229736339,-2.89680429461,-3.40341918012,-5.48883948498,-5.06519830645,-1.35221134128,-4.14885317027,0.662548263548},
{4.39262525396,-1.54326017625,-6.26442632952,-3.12468756888,-6.05151076948,-2.71671672604,5.30286941635,-4.61543359305,3.50331823342,6.08676455011,-6.57596055236,-0.367208110948,-5.66877635575,-3.2141565298,2.88025706574,-0.858097837416,5.80205993762,-4.72707087065,-4.72689704036,-3.02513355739,-5.11487542032,-4.21810981122,2.70845919384,1.15145340659,-4.19672110381,1.54863719866},
{4.66506054565,0.162412907805,-4.91882476648,5.49820423875,-8.87542808941,1.05581613937,-5.70011055932,-0.154119152404,-9.8063994159,6.6877483916,-4.3082328811,-3.21462767585,-3.31243302241,5.55529476276,-7.02608335154,3.56889883975,-4.21729126113,-2.38156491498,3.69688546853,-2.32225576849,-4.19632599459,2.74239972182,1.749904267,-3.71392662101,-3.60218780439,-4.1676274119},
{-2.05281096436,-1.44007355771,2.31850196159,-2.28073609537,-7.25992690794,-5.84268445468,2.06414743078,5.46056213612,-6.22277000118,1.11954265236,-2.72635788997,-1.41376110692,1.98046637339,4.9868431906,2.03839294425,-2.7509329373,2.71854120179,4.77027045136,-2.60878699891,-1.87716777948,2.00715118744,-1.14955968323,-3.25567840343,1.80822821543,-5.62471280821,-3.85200113651},
{-0.996613990954,1.31945682201,5.51805019359,-1.03961104799,5.71129816815,4.99499369164,1.12547062134,-5.46953365118,-2.53592496707,0.752701927061,-1.80027499534,-2.65694108224,-6.32993326915,-4.96516126253,5.36981956207,2.20875762266,-5.25204765938,1.50052941486,1.46883764691,5.08534742356,-6.49522886492,-3.54136313978,-2.43173146555,-4.97695117542,-4.19770075956,3.06328325035},
{-3.50203354913,-1.30452545852,-5.12102568182,-5.56716253499,-0.675443085766,1.01358872038,1.28859471058,-1.5504225738,-5.18096422693,0.601611311157,-0.562468823741,2.75188904881,-4.49710504522,-0.50735336299,-6.32536237657,-4.4789649817,-4.7589774398,-2.40968838316,1.28534336177,-2.05807025764,2.24971535649,-5.91745608062,0.628374768803,-0.133950068646,1.70439382698,0.386186297223},
{1.11928469113,1.09235918106,1.81740034331,-6.18419599391,1.3570230989,-4.44206422657,5.0543555393,2.92464495461,4.99861384658,-6.09637657939,2.17685822977,2.38931606456,-2.93964327311,-6.83213583466,-9.64631982802,-0.40859077959,2.44299739721,3.46705999451,0.623740332115,-5.12852889637,-7.18776476858,1.02871583004,-1.18209294429,-6.8634881076,-5.19495053661,-4.65401468217},
{1.03633886256,-1.73003940285,1.12058450112,1.79944820675,-4.00765310326,-1.89279984026,-3.45833821506,-3.26704513024,-6.16212468659,-3.71343684414,-1.14752188816,0.623041433915,2.42410249605,-0.845038184353,0.0127725693742,-6.7112765903,0.0176432053276,-2.76216460569,1.58285923432,0.366550643216,0.12037926537,-5.99790550437,-1.84099186006,-1.59245302906,-3.69929437383,-0.863015437257},
{2.17581866229,-2.00538772198,-2.55752389982,-1.91550389633,-1.59227152847,-3.6604070931,2.78926697984,-0.858844427993,7.08812957202,1.8721660473,-2.69046900041,-1.64199988018,-1.62680788168,-1.07323872653,1.96814511231,0.594412962511,-1.64992521151,-2.61026307553,-1.18384115607,4.00664199397,0.603791864116,3.01106571774,-0.339878607793,-1.65733311524,-3.03050602039,0.0304548462551},
{0.0161871105077,-3.55358365786,-1.05882849147,-3.38009084875,-2.97383371975,-4.12206766505,-1.51955316276,-4.09892319564,-3.59252359206,-2.09443709143,-2.25944475194,-0.907252012907,-1.01531992516,-4.77871168726,-2.17647948162,-4.81554334115,-3.4873775762,-2.08951184844,-0.508358816674,-2.52255453064,-0.329437413321,-1.62254946469,-2.38257466222,-0.425167030429,-3.18053390446,-2.05261541282},
{1.38936472899,3.10111385473,-4.34162127776,-3.60356759356,4.25920544384,-1.11498257942,-4.03549950442,1.06335920055,6.27567459094,-2.38807978766,-0.545396249606,-6.3262570284,-2.22459764423,1.20539776663,-0.0947962566115,2.77122310629,-1.16368991409,0.866522949017,1.5730882498,1.50199867915,-4.91559425807,-2.8282260062,1.80643673518,1.72103728668,0.82612234821,-6.64211548544},
{-2.83967181512,2.71864146534,-0.983326264114,-2.26981530808,1.0411485228,-2.47824129343,-4.56922983513,-0.701201790809,3.98498183903,1.62520817051,-6.53828635434,-2.30849732618,7.52523406491,-4.3238320989,-1.65721292076,-1.1274136221,5.11593474321,-5.14982326999,-2.1505147529,3.39797977275,-0.430882805233,3.8975047645,-2.30126214648,-1.58530793712,3.02068035152,0.923044954684},
{-1.47082108925,-4.45711776719,2.52027161059,0.671050634359,2.42006181278,-3.61516067377,-0.999547772281,-0.233706975162,-0.246036594192,-4.48167891134,3.0900535024,2.00416341728,-2.34975965404,3.37577721491,-2.04473507686,-5.68447570371,-3.11529261589,-8.80642141421,-0.107762149658,1.42427856921,3.6104198985,2.06557780174,0.94127849512,3.53597476349,-3.40354491493,-2.3384482988},
{-2.32593260212,-7.23748354404,0.69044518421,3.0330529823,-11.9933829816,6.24757400795,-5.05779037621,-7.87107263568,2.75806075259,-2.034818918,-0.695600938838,-3.41895558476,-10.237263968,-1.85442679409,-2.62482266589,1.82980853791,2.21486823081,-1.17280986214,-5.41837793763,0.589269478769,2.26766620335,2.6179941403,-0.194599082533,-1.20159059833,1.30474604865,-1.47948811553},
{-2.12905069348,-3.91262070936,-2.48422231902,-1.93664270598,-1.83998021862,-0.69546111606,-1.0137556586,-1.30696530826,-1.83420857277,0.17882444858,-10.4143427662,-0.249475667945,-0.794631112963,-1.5006530315,-0.562314866969,-2.51946103968,-3.22699892522,-3.26027379569,-0.207620063841,-8.82600113319,-1.74160861114,-0.395465100576,-7.27838889128,-4.43472400963,3.63808420506,0.317117242815},
{-8.43286456361,-0.583814818899,-0.939377070702,-2.15704142473,1.42932774886,1.11294877962,-1.7269490406,-3.12987415683,-3.05255419601,-2.40706338867,4.44647671273,-5.49687155833,0.129941683334,1.39483392939,-0.851426653049,-0.420819354043,-0.385882881142,-6.66496743103,-0.188820360039,2.06421201973,1.84419666441,-1.67344752308,1.79779533764,-8.2958899527,0.929822443098,-4.97463094003},
{-2.74456630028,0.620858234148,-0.555777435038,5.41918588148,-3.2924906972,-4.74678193239,-1.83685580942,-2.60356934211,-0.240341171101,-1.14240926977,3.78511666881,-1.56472292039,-0.924712412718,0.225400603611,-3.8964295514,-3.49373715325,-3.08909463912,4.23308970857,-0.0721146728281,0.760574770148,-2.22372495571,-3.41938193857,-6.7140360613,3.53530401391,4.98430080905,2.13831693896},
{1.15027521841,-9.57193038505,-0.394523116954,-4.8686577224,3.32226499898,6.65581838044,-2.75677296288,6.38505187211,-4.96671318671,-1.43774498628,1.36949117187,-5.04646443351,2.46192327424,1.01977023629,-4.0648751244,-5.00118948145,-3.19563160788,3.72630975626,-3.06069389083,-1.65319081978,-5.15265543113,3.23443061515,1.29024464679,0.717734342645,-0.848450537254,4.03342068861},
{-4.77549397209,5.67041861911,-4.41526370949,2.96342255873,-1.19916075003,-2.24185175235,4.13771860512,10.4842328976,-2.21876860315,-2.92057554384,0.208205281717,-3.52745584119,-3.82127485583,-5.40862502249,0.556352295046,1.65774276718,-2.14989919509,-5.818150052,-3.77549481664,-2.00615471046,1.92385806679,-1.54316725402,4.42988956239,-1.00821492904,-3.42798128031,1.65253983971}
};
const double* update(const double inputs[NI-1])
{
double ah[NH];
static double ao[NO];
for(U32 j=0; j<NH; j++)
{
double sum=wi[NI-1][j];
for(U32 i=0; i<NI-1; i++)
sum += inputs[i]*wi[i][j];
ah[j] = 1.0/(1.0+exp(-sum));
}
for(U32 k=0; k<NO; k++)
{
double sum=0.0;
for(U32 j=0; j<NH; j++)
{
sum += ah[j]*wo[j][k];
ao[k] = 1.0/(1.0+exp(-sum));
}
}
return ao;
}
// [int(round(math.tan(math.pi/4*(i/64.))*10000)) for i in range(64)]
struct Tan {I32 a,b;};
const Tan tans[]= {
{ 0, -1},{ -1, 0},{10000,-10000},{-10000,-10000}, // extremes, +- pi/4
{-10000,- 123},{ 123,-10000},{- 123,-10000},{10000,- 123},
{-10000,- 245},{ 245,-10000},{- 245,-10000},{10000,- 245},
{-10000,- 368},{ 368,-10000},{- 368,-10000},{10000,- 368},
{-10000,- 491},{ 491,-10000},{- 491,-10000},{10000,- 491},
{-10000,- 614},{ 614,-10000},{- 614,-10000},{10000,- 614},
{-10000,- 738},{ 738,-10000},{- 738,-10000},{10000,- 738},
{-10000,- 861},{ 861,-10000},{- 861,-10000},{10000,- 861},
{-10000,- 985},{ 985,-10000},{- 985,-10000},{10000,- 985},
{-10000,- 1109},{ 1109,-10000},{- 1109,-10000},{10000,- 1109},
{-10000,- 1233},{ 1233,-10000},{- 1233,-10000},{10000,- 1233},
{-10000,- 1358},{ 1358,-10000},{- 1358,-10000},{10000,- 1358},
{-10000,- 1483},{ 1483,-10000},{- 1483,-10000},{10000,- 1483},
{-10000,- 1609},{ 1609,-10000},{- 1609,-10000},{10000,- 1609},
{-10000,- 1735},{ 1735,-10000},{- 1735,-10000},{10000,- 1735},
{-10000,- 1862},{ 1862,-10000},{- 1862,-10000},{10000,- 1862},
{-10000,- 1989},{ 1989,-10000},{- 1989,-10000},{10000,- 1989},
{-10000,- 2117},{ 2117,-10000},{- 2117,-10000},{10000,- 2117},
{-10000,- 2246},{ 2246,-10000},{- 2246,-10000},{10000,- 2246},
{-10000,- 2375},{ 2375,-10000},{- 2375,-10000},{10000,- 2375},
{-10000,- 2505},{ 2505,-10000},{- 2505,-10000},{10000,- 2505},
{-10000,- 2636},{ 2636,-10000},{- 2636,-10000},{10000,- 2636},
{-10000,- 2767},{ 2767,-10000},{- 2767,-10000},{10000,- 2767},
{-10000,- 2900},{ 2900,-10000},{- 2900,-10000},{10000,- 2900},
{-10000,- 3033},{ 3033,-10000},{- 3033,-10000},{10000,- 3033},
{-10000,- 3168},{ 3168,-10000},{- 3168,-10000},{10000,- 3168},
{-10000,- 3304},{ 3304,-10000},{- 3304,-10000},{10000,- 3304},
{-10000,- 3440},{ 3440,-10000},{- 3440,-10000},{10000,- 3440},
{-10000,- 3578},{ 3578,-10000},{- 3578,-10000},{10000,- 3578},
{-10000,- 3717},{ 3717,-10000},{- 3717,-10000},{10000,- 3717},
{-10000,- 3857},{ 3857,-10000},{- 3857,-10000},{10000,- 3857},
{-10000,- 3999},{ 3999,-10000},{- 3999,-10000},{10000,- 3999},
{-10000,- 4142},{ 4142,-10000},{- 4142,-10000},{10000,- 4142},
{-10000,- 4287},{ 4287,-10000},{- 4287,-10000},{10000,- 4287},
{-10000,- 4433},{ 4433,-10000},{- 4433,-10000},{10000,- 4433},
{-10000,- 4580},{ 4580,-10000},{- 4580,-10000},{10000,- 4580},
{-10000,- 4730},{ 4730,-10000},{- 4730,-10000},{10000,- 4730},
{-10000,- 4881},{ 4881,-10000},{- 4881,-10000},{10000,- 4881},
{-10000,- 5034},{ 5034,-10000},{- 5034,-10000},{10000,- 5034},
{-10000,- 5188},{ 5188,-10000},{- 5188,-10000},{10000,- 5188},
{-10000,- 5345},{ 5345,-10000},{- 5345,-10000},{10000,- 5345},
{-10000,- 5504},{ 5504,-10000},{- 5504,-10000},{10000,- 5504},
{-10000,- 5665},{ 5665,-10000},{- 5665,-10000},{10000,- 5665},
{-10000,- 5828},{ 5828,-10000},{- 5828,-10000},{10000,- 5828},
{-10000,- 5994},{ 5994,-10000},{- 5994,-10000},{10000,- 5994},
{-10000,- 6162},{ 6162,-10000},{- 6162,-10000},{10000,- 6162},
{-10000,- 6332},{ 6332,-10000},{- 6332,-10000},{10000,- 6332},
{-10000,- 6506},{ 6506,-10000},{- 6506,-10000},{10000,- 6506},
{-10000,- 6682},{ 6682,-10000},{- 6682,-10000},{10000,- 6682},
{-10000,- 6861},{ 6861,-10000},{- 6861,-10000},{10000,- 6861},
{-10000,- 7043},{ 7043,-10000},{- 7043,-10000},{10000,- 7043},
{-10000,- 7228},{ 7228,-10000},{- 7228,-10000},{10000,- 7228},
{-10000,- 7417},{ 7417,-10000},{- 7417,-10000},{10000,- 7417},
{-10000,- 7608},{ 7608,-10000},{- 7608,-10000},{10000,- 7608},
{-10000,- 7804},{ 7804,-10000},{- 7804,-10000},{10000,- 7804},
{-10000,- 8003},{ 8003,-10000},{- 8003,-10000},{10000,- 8003},
{-10000,- 8207},{ 8207,-10000},{- 8207,-10000},{10000,- 8207},
{-10000,- 8414},{ 8414,-10000},{- 8414,-10000},{10000,- 8414},
{-10000,- 8626},{ 8626,-10000},{- 8626,-10000},{10000,- 8626},
{-10000,- 8842},{ 8842,-10000},{- 8842,-10000},{10000,- 8842},
{-10000,- 9063},{ 9063,-10000},{- 9063,-10000},{10000,- 9063},
{-10000,- 9290},{ 9290,-10000},{- 9290,-10000},{10000,- 9290},
{-10000,- 9521},{ 9521,-10000},{- 9521,-10000},{10000,- 9521},
{-10000,- 9758},{ 9758,-10000},{- 9758,-10000},{10000,- 9758},
};
inline I32 intersectx(I64 a1, I64 b1, I64 v1, I64 a2, I64 b2, I64 v2)
{
return I32((b2*v1-b1*v2) / (a1*b2-a2*b1));
}
inline I32 intersecty(I64 a1, I64 b1, I64 v1, I64 a2, I64 b2, I64 v2)
{
return I32((a1*v2-a2*v1) / (a1*b2-a2*b1));
}
class Im
{
enum {SX=320,SY=36};
enum {BLACK=0,WHITE=1,OBJECT0=3};
U8 _img[200][200];
U8 _gerade[SY][SX];
U32 _objects;
double _mindistance;
U32 _minj;
struct M
{
bool inuse;
I32 minx,miny,minv,maxx,maxy,maxv;
//TODO: M() : inuse(false) {}
};
M _m[countof(tans)];
public:
Im(char lines[200][256])
{
//assert(lines.size()==200);
for(U32 y=0; y<200; y++)
{
const char* s = lines[y];
assert(strlen(s)==200);
for(U32 x=0; x<200; x++)
{
_img[y][x] = s[x]=='X' ? WHITE : BLACK;
}
}
_objects = 0;
_mindistance = 0.0;
memset(_m, 0, sizeof(_m)); // TODO: remove it
}
inline U8 px(I32 x, I32 y) const
{
if (0<=x && x<200 && 0<=y && y<200)
return _img[y][x];
else
return 0;
}
inline void setpx(I32 x, I32 y, U8 c)
{
if (0<=x && x<200 && 0<=y && y<200)
_img[y][x] = c;
}
U32 assume(I32 x, I32 y, U8 oldcolor, U8 color)
{
assert(px(x,y)==oldcolor);
setpx(x, y, color);
U32 lenobject = 1;
if( px(x-1,y)==oldcolor ) lenobject += assume(x-1,y,oldcolor,color);
if( px(x,y-1)==oldcolor ) lenobject += assume(x,y-1,oldcolor,color);
if( px(x+1,y)==oldcolor ) lenobject += assume(x+1,y,oldcolor,color);
if( px(x,y+1)==oldcolor ) lenobject += assume(x,y+1,oldcolor,color);
return lenobject;
}
void findobjects()
{
_objects = 0;
// a la derecha
for(U32 x=0; x<200; x++)
{
for(U32 y=0; y<200; y++)
{
if(px(x,y)==WHITE)
{
if( assume(x, y, WHITE, OBJECT0+_objects)<50 )
assume(x, y, OBJECT0+_objects, BLACK);
else
_objects ++;
}
}
}
//printf("_objects=%d\n", _objects);
}
// TODO: convex hull i dalshe po nemu, vnutrennie tochki tut ne interesny
void bound()
{
U32 xxx=0,yyy=0,nnn=0; // to calc center
for(U32 y=0; y<200; y++)
{
U32 xmin=-1, xmax=-1;
for(U32 x=0; x<200; x++)
{
if( px(x,y)!=BLACK )
{
if(xmin==-1) xmin=x;
xmax=x;
}
}
if(xmin!=-1)
{
for(U32 i=0; i<2; i++)
{
const U32 x = i==0 ? xmin : xmax;
xxx += x;
yyy += y;
nnn += 1;
for(U32 j=0; j<countof(tans); j++)
{
const I32 a = tans[j].a;
const I32 b = tans[j].b;
const I32 v = a*x + b*y;
if(!_m[j].inuse)
{
_m[j].inuse = true;
_m[j].minx = x; _m[j].miny = y; _m[j].minv = v;
_m[j].maxx = x; _m[j].maxy = y; _m[j].maxv = v;
}
else if(v < _m[j].minv)
{
_m[j].minx = x; _m[j].miny = y; _m[j].minv = v;
}
else if(v > _m[j].maxv)
{
_m[j].maxx = x; _m[j].maxy = y; _m[j].maxv = v;
}
}
}
}
}
const U32 xcenter=(xxx+nnn/2)/nnn;
const U32 ycenter=(yyy+nnn/2)/nnn;
//printf("center=%d %d nnn=%d\n", xcenter, ycenter, nnn);
// vybiraem liniju po min rasstojaniju mezhdu minimalnoj i maximalnoj parallelnymi prjamyli
// FIXED: mezhdu maximalnoj i geom centrom
_minj=-1;
double mindist;
for(U32 j=0; j<countof(tans); j++)
{
const I32 a = tans[j].a;
const I32 b = tans[j].b;
//const I32 vmin = m[j].minv;
const I32 vmin = a*xcenter + b*ycenter;
const I32 vmax = _m[j].maxv;
assert(vmax>vmin);
const double distance = double(vmax-vmin)*double(vmax-vmin) / double(a*a+b*b);
//printf("a,b,dist=%d %d %d %d %f\n", a,b,vmin,vmax,distance);
if(_minj==-1 || distance<mindist)
{
mindist = distance;
_minj = j;
}
}
assert(_minj!=-1);
// la distancia entre las lineas
const I32 a = tans[_minj].a;
const I32 b = tans[_minj].b;
const I32 vmin = _m[_minj].minv;
const I32 vmax = _m[_minj].maxv;
//printf("a,b=%d %d %d %d\n", a,b,vmin,vmax);
assert(vmax>vmin);
const double distance = double(vmax-vmin)*double(vmax-vmin) / double(a*a+b*b);
_mindistance = sqrt(distance);
assert(_mindistance>0);
}
void make5x7(double arr5x7[7*5], U32 xmin, U32 ymin, U32 width, U32 height, U8 color)
{
#if 1
U32 dat[7*5]={0};
U32 siz[7*5]={0};
for(U32 y=0; y<height; y++)
for(U32 x=0; x<width; x++)
{
U32 i = (y*7/height)*5 + x*5/width;
assert(0<=i && i<5*7);
if(_gerade[y+ymin][x+xmin]==color)
dat [i] ++;
siz [i] ++;
}
for(U32 i=0; i<7*5; i++)
{
arr5x7[i] = double(dat[i]) / (siz[i]+1);
assert(0<=arr5x7[i] && arr5x7[i]<=1.0);
}
#else
U32 dat[7][5]={0};
for(U32 y=0; y<height*7; y++)
for(U32 x=0; x<width*5; x++)
{
if(_gerade[y/7+ymin][x/5+xmin]==color)
dat[y/height][x/width] ++;
}
const double WH = double(5*7);
for(U32 y=0; y<7; y++)
for(U32 x=0; x<5; x++)
arr5x7[y*5+x] = dat[y][x] / WH;
#endif
}
U8 analiz(U32 xmin, U32 ymin, U32 width, U32 height, U8 color, bool strict=true)
{
double arr5x7[7*5];
assert(xmin<SX);
assert(ymin<SY);
assert(xmin+width<=SX);
assert(ymin+height<=SY);
make5x7(arr5x7, xmin, ymin, width, height, color);
const double* outs = update(arr5x7);
U32 o1, o2;
double v1=-1.0, v2=-1.0;
for(U32 i=0; i<26; i++)
{
if(v1<outs[i]) v1=outs[o1=i];
}
for(U32 i=0; i<26; i++)
{
if(o1!=i && v2<outs[i]) v2=outs[o2=i];
}
if(strict)
if(v1>=0.95 && v1>=v2*2.00)
{
return o1+'A';
} else
return '@';
else
if(v1>=0.4 && v1>=v2*1.60)
{
return o1+'A';
} else
return '@';
}
void transform(char res[])
{
res[0] = '\0';
const I32 a = tans[_minj].a;
const I32 b = tans[_minj].b;
const double c = sqrt(double(a*a+b*b));
const U32 perpendicularj = _minj ^ 1;
//printf("a,b,v = %d %d %d\n", a,b,_m[_minj].maxv);
//printf("_|_ = %d %d %d %d\n", tans[perpendicularj].a,tans[perpendicularj].b,_m[perpendicularj].minv,_m[perpendicularj].maxv);
// tochki peresechenija verhnej linii opisannogo prjamougolnika s levoj i pravoj storonami
const I32 x1=intersectx(a,b,_m[_minj].maxv, tans[perpendicularj].a,tans[perpendicularj].b,_m[perpendicularj].minv);
const I32 y1=intersecty(a,b,_m[_minj].maxv, tans[perpendicularj].a,tans[perpendicularj].b,_m[perpendicularj].minv);
const I32 x2=intersectx(a,b,_m[_minj].maxv, tans[perpendicularj].a,tans[perpendicularj].b,_m[perpendicularj].maxv);
const I32 y2=intersecty(a,b,_m[_minj].maxv, tans[perpendicularj].a,tans[perpendicularj].b,_m[perpendicularj].maxv);
// levaja iz nih
I32 x0,y0;
if(x1<x2) x0=x1,y0=y1; else x0=x2,y0=y2;
//printf("x0,y0 = %d %d\n", x0,y0);
//printf("x1,y1 = %d %d\n", x1,y1);
//printf("x2,y2 = %d %d\n", x2,y2);
//return;
//U8 _gerade[SY][SX];
memset(_gerade, BLACK, sizeof(_gerade));
const U32 FONTSIZE=32;
const double scale = FONTSIZE/_mindistance;
const double kscale = 1./c/scale;
const double akscale = a*kscale;
const double bkscale = b*kscale;
//printf("akscale,bkscale = %f %f\n", akscale,bkscale);
struct ObjBound {
bool inuse;
U32 minx,miny,maxx,maxy;
ObjBound() : inuse(false) {}
};
ObjBound* objbounds = new ObjBound[_objects];
// affine transform
for(U32 x=0; x<SX; x++)
{
const double xakscale = akscale*x;
const double xbkscale = bkscale*x;
for(U32 y=0; y<SY; y++)
{
const I32 xx=x0-1+I32(-xbkscale-akscale*y);
const I32 yy=y0-1+I32(xakscale-bkscale*y);
const U8 color = px(xx,yy);
//printf("xx,yy = %d %d %d\n", xx,yy,color);
_gerade[y][x] = color;
if(color>=OBJECT0)
{
assert(U32(color)-OBJECT0<_objects);
ObjBound& o = objbounds[color-OBJECT0];
//printf("color-OBJECT0=%d\n",color-OBJECT0);
if(!o.inuse)
{
o.inuse = true;
o.minx=o.maxx=x;
o.miny=o.maxy=y;
} else
{
o.minx=min(o.minx,x);
o.maxx=max(o.maxx,x);
o.miny=min(o.miny,y);
o.maxy=max(o.maxy,y);
}
}
}
}
//TODO: qsort(objbounds)
for(U32 o=0; o<_objects; o++)
{
assert(objbounds[o].inuse);
const U8 color = OBJECT0+o;
const U32 minx = objbounds[o].minx;
const U32 maxx = max(minx+(FONTSIZE*100/256), objbounds[o].maxx);
const U32 miny = objbounds[o].miny;
const U32 maxy = objbounds[o].maxy;
const U32 width = maxx+1-minx;
const U32 height = maxy+1-miny;
U8 letter = analiz(minx,miny,width,height,color,false);
if( letter!='@' && width<=50 && (width<=44 || letter=='W') )
{
char sz[2]={letter,0};
strcat(res, sz);
} else
{
// dopustim chto tut 2 bukby (TODO: a mozhet i 3-4)
U8 hist2[26][26] = {0};
U32 histsum = 0;
//printf("width=%d -> %d ",width, max(12u,width-50));
for(U32 w=max(12,int(width-50)); w<50 && w<width-12; w++)
{
U8 letter1=analiz(minx,miny,w,height,color);
if( letter1!='@' && (w<=44 || letter=='W') )
{
U8 letter2=analiz(minx+w,miny,width-w,height,color);
if( letter2!='@' && (width-w<=44 || letter2=='W') )
{
hist2[letter1-'A'][letter2-'A'] ++;
histsum ++;
}
}
}
if(histsum>=4)
{
_zwei:
U8 maxhist=0;
char sz[3]={'@','@',0};
for(U32 i=0; i<26; i++)
for(U32 j=0; j<26; j++)
{
if(hist2[i][j]>maxhist)
{
maxhist=hist2[i][j];
sz[0]='A'+i;
sz[1]='A'+j;
}
}
strcat(res, sz);
} else
{
U8 hist3[26][26][26] = {0};
U32 histsum3 = 0;
for(U32 w1=max(12,int(width-2*50)); w1<50 && w1<width-12; w1+=1)
{
U8 letter1=analiz(minx,miny,w1,height,color);
if( letter1!='@' && (w1<=44 || letter=='W') )
{
for(U32 w2=max(12,int(width-w1-50)); w2<50 && w2<width-w1-12; w2+=1)
{
U8 letter2=analiz(minx+w1,miny,w2,height,color);
if( letter2!='@' && (w2<=44 || letter2=='W') )
{
const I32 w3 = width-w1-w2;
U8 letter3=analiz(minx+w1+w2,miny,w3,height,color);
if( letter3!='@' && (w3<=44 || letter3=='W') )
{
hist3[letter1-'A'][letter2-'A'][letter3-'A'] ++;
histsum3 ++;
}
}
}
}
}
if(histsum3>=4)
{
U8 maxhist=0;
char sz[4]={'@','@','@',0};
for(U32 i=0; i<26; i++)
for(U32 j=0; j<26; j++)
for(U32 k=0; k<26; k++)
{
if(hist3[i][j][k]>maxhist)
{
maxhist=hist3[i][j][k];
sz[0]='A'+i;
sz[1]='A'+j;
sz[2]='A'+k;
}
}
strcat(res, sz);
} else
{
goto _zwei;
}
}
}
}
}
};
main(int argc, char** argv)
{
#ifndef ONLINE_JUDGE
intptr_t h;
_finddata_t fileinfo;
int sum=0, sumok=0;
if ( h=_findfirst("imgset/*.txt", &fileinfo) )
do {
if(fileinfo.size==41171)
{
char sz[200];
strcpy(sz, "imgset/");
strcat(sz, fileinfo.name);
printf("%-24s", sz );
char buf[0x10000] = {};
char img[200][256];
FILE*f =fopen(sz, "rb");
assert(f);
fread(buf, 41171, 1, f);
fclose(f);
int x=0, y=0;
for(int i=0; i<41171; i++)
{
if(buf[i]=='X' || buf[i]=='.')
{
img[y][x] = buf[i];
x++;
if(x>=200) {
x = 0;
y ++;
if(y>=200) break;
}
}
}
assert(y==200);
// printf("%d\n", n );
char sz2[200];
Im im(img);
im.findobjects();
im.bound();
im.transform(sz2);
bool ok = 0==memcmp(sz+7, sz2, strlen(sz2)) && sz[7+strlen(sz2)]=='.';
sumok += ok;
sum ++;
printf("%-8s %s\n", sz2, ok?"ok":"fail");
}
} while( !_findnext(h, &fileinfo) );
printf("%d/%d\n", sumok, sum);
return 1;
#endif
#ifndef ONLINE_JUDGE
char name[256];
#ifdef _WIN32
strcpy(name, strrchr(argv[0],'\\')+1);
#else
strcpy(name, strrchr(argv[0],'/')+1);
#endif
strcpy(strrchr(name,'.')+1, "txt");
freopen(name,"r",stdin);
#endif
char sz[100];
unsigned ncases;
gets(sz);
sscanf(sz,"%d", &ncases);
while(ncases--)
{
char img[200][256];
for(U32 y=0; y<200; )
{
gets(img[y]);
if(img[y][0])
{
for(char*p=img[y]+strlen(img[y])-1; p>=img[y] && *p<0x20; p--) *p='\0';
assert(strlen(img[y])==200);
y++;
}
}
Im im = Im(img);
im.findobjects();
im.bound();
im.transform(sz);
printf("%s\n", sz);
}
}
|
|||
| ||||