Common Board| Show all threads Hide all threads Show all messages Hide all messages | | JAVA PROBLEM - "Time Limit Exceeded" | Qambar Raza | 1001. Reverse Root | 1 Sep 2008 02:14 | 2 | import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException
{
new Main().run();
}
StreamTokenizer in;
PrintWriter out;
void run() throws IOException
{
in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
out = new PrintWriter(new OutputStreamWriter(System.out));
solve();
out.flush();
}
void solve() throws IOException
{
LinkedList<Double> myArr = new LinkedList<Double>();
while(in.nextToken() != StreamTokenizer.TT_EOF)
{
myArr.add(Math.sqrt((double)(in.nval)));
}
myArr.add(0.0);
ListIterator iterator = myArr.listIterator(myArr.size() - 1);
while (iterator.hasPrevious())
{
out.printf("%.4f\n", iterator.previous());
}
}
}
I read the FAQS and other post but still cannot figure out whats the problem its working fine on my test cases which are as follows:
Description: First 4 are input numbers rest is output.
Test Case # 1:
2
5
3
5
2.2361
1.7321
2.2361
1.4142
Test Case # 2:
1427
0
876652098643267843
5276538
2297.0716
936297014.1164
0.0000
37.7757
Test Case # 3:
1 2 3 4
2.0000
1.7321
1.4142
1.0000
Test Case # 4:
2
4
64
49
7.0000
8.0000
2.0000
1.4142
Why am i getting the time limit exceed error ? You can solve this problem on Java in two ways:
1. Use NumberFormat:
NumberFormat nf = NumberFormat.getInstance(Locale.US);
nf.setMaximumFractionDigits(6);
nf.setGroupingUsed(false);
out.println(nf.format(x));
You can get AC in 1.14 sec in such way
2. Use BigDecimal:
out.println(BigDecimal.valueOf(x).setScale(6, RoundingMode.HALF_UP));
You can get AC in 1.375 sec in such way | | Can we have negative numbers in the matrix? | LSBG | 1625. Hankel Matrix | 1 Sep 2008 02:06 | 5 |
Edited by author 17.08.2008 16:05 Apparently we are not allowed to use negative numbers. | | Minor fix | Denis Koshman | 1271. Sailing Directions | 1 Sep 2008 02:03 | 2 | Eng. problem statement
"namely its angle described in the second input line"
"its angle" should be "its corner" or "its vertex" or "its point" | | If you have WA10 | Denis Koshman | 1074. Very Short Problem | 31 Aug 2008 17:01 | 1 | Replace isdigit(s[i]) with isdigit((byte)s[i])
where
typedef unsigned char byte;
ctype.h functions are buggish with signed char. | | When should I output the sign? | Vinicius Fortuna | 1074. Very Short Problem | 31 Aug 2008 16:46 | 2 | The problem statement says that the sample input
-0.051e0
1
gives 0.0 as output, and not -0.0
Is that right or the sample is wrong?
If it was
-0.051e0
2
what should I output? -0.05 or 0.05?
Thanks a lot
Vinicius Fortuna
IC-Unicamp You should output '-' sign when original number is negative and output contains at least one non-zero digit. | | Can receiver be placed higher than 32000?(-) | Kit | 1168. Radio Stations | 31 Aug 2008 15:51 | 2 | My solution gets AC in both cases, i think there are no tests where receiver can be placed higher than 32000. | | Что за тесты? | AndreySUrSU | 1509. Domino Recognition | 31 Aug 2008 08:59 | 9 | Я из команды SUrSU 1.
Не понятно, что у вас за тесты на эту задачу.
Говорится, что координаты даны с точностью до 5 знаков, мы предполагали, что достаточно точно.
Посылали с большой точностью на контесте, это было в самом конце контеста, как-то не успели подумать, что можно и с маленькой точностью послать, к тому же еще были заняты написанием задачи И.
Теперь я написал такое же решение, посылал с точностью 10^-6 вроде - не принималась, 10^-2 - принялась.
Что за бред???? Мда, это все конечно интересно, но мое решение например вообще нигде не использует точность и AC c первого раза. Но правда и задача очень специфическая. Все верно, если входные данные зашумлены на 1E-5, то требовать от решения 1E-6 неверно Это у нас используется для проверки коэффициента подобия.
1E-4 - 8WA
1E-3 - 44WA
Все-таки странно.
Почему именно 1E-2 проходит, а 1E-3 - плохая точность. Посчитаем погрешность вычисления коэффициента подобия: погрешность координат 1e-5, значит, погрешность расстояния — 3e-5, погрешность коэффициента при максимальном стократном отношении размеров — 3e-3.
Понятно, что точности 1e-3 недостаточно для сравнения коэффициентов подобия.
Edited by author 01.11.2006 17:41 Что-то я не совсем понимаю это.
У нас есть эталонная доминошка со стороной 1. Координаты на ней точные. 1<=K<=100. Любые доминошки, с меньшими расстояниями не подходят.
Рассматриваем доминошки с большими расстояниями, они вроде бы, по логике, должны быть более точно засняты. Получается, что чем крупнее снимок, тем хуже точность, странно.
По-моему у крупного снимка относительная точность больше, те с ростом коэффициента точность растет.
Или я не прав? I tried to follow the topic but the translator russian - english was not enough. I have a program which gets WA in test 44. Actually I proved changing precision issues and the best I got was WA in test 90, so I think the only bug in the code is about precision.
The function that deals with precision in my code is:
bool check(par *q, double t) {
int i, j, orden[12];
bool usado[12];
memset(usado, 0, sizeof(usado));
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) if (!usado[j])
if (dist(q[i].first - p[j].first, q[i].second - p[j].second) < eps) break;
if (j == n) return false;
usado[j] = true;
}
return true;
}
Array p keeps the input points and array q the points in a possible domino tile. The function check returns if the points in both arrays are "more or less" the same
The function dist is:
double dist(double x, double y) {
return fabs(x)+ fabs(y);
}
and the eps is defined to be 1e-3
It would be great if anybody who got AC explains how he dealt with precision in his code This is not precision problem, but wrong approach problem.
Input coordinates do not define points. They define a SET of points whose precise coordinates become input values after rounding. E.g. pair (1.2345;6.7890) defines half-open square [1.23445;1.23455) x [6.78895;6.78905). All points within this square become (1.2345;6.7890) after rounding.
You task is to find all dies with 1<=L<=100 whose precise dot coordinates fall into these half-open squares with one-to-one relationship. | | 1st question. (There're two kinds of understandings.) | Safe Bird | 1415. Mobile Life | 31 Aug 2008 08:26 | 16 | If there're two stations that would give the signal as VIOLET, but one is stronger.
1. we choose the stronger.
2. we choose the one according to their names.
which one is right? anyway, i got wa on 4 on both of the meanings.
Edited by author 01.11.2005 21:21 If the segment which our hero goes just tangentalled to the curves of change of the current signal's level, should I output twice "Signal Changed...."?
The condition is the same as above, if he just touches the curve of ORANGE, should I output:
Cell changed. CELL_ID:...., SIGNAL_LEVEL:ORANGE
Signal changed. SIGNAL_LEVEL:RED
?
Edited by author 01.11.2005 21:21 if we change the sample input to:
5 5 -20 -20
-20 -20 5 5
then we have:
Power on. CELL_ID:Znaika, SIGNAL_LEVEL:GREEN
Signal changed. SIGNAL_LEVEL:YELLOW
Signal changed. SIGNAL_LEVEL:ORANGE
Signal changed. SIGNAL_LEVEL:RED
Cell changed. CELL_ID:Romashka, SIGNAL_LEVEL:YELLOW
Signal changed. SIGNAL_LEVEL:ORANGE
Signal changed. SIGNAL_LEVEL:RED
// HERE, should I output the following line?
// I think we don't need, but by the description, we should...
Cell changed. CELL_ID:Romashka, SIGNAL_LEVEL:ORANGE
Signal changed. SIGNAL_LEVEL:YELLOW
Signal changed. SIGNAL_LEVEL:GREEN
Signal changed. SIGNAL_LEVEL:BLUE
Signal changed. SIGNAL_LEVEL:INDIGO
Signal changed. SIGNAL_LEVEL:VIOLET
Signal changed. SIGNAL_LEVEL:INDIGO
Signal changed. SIGNAL_LEVEL:BLUE
Signal changed. SIGNAL_LEVEL:GREEN
Signal changed. SIGNAL_LEVEL:YELLOW
Signal changed. SIGNAL_LEVEL:ORANGE If when the mobile turns on, it gets RED even to the closest station. Should I output:
Power on. CELL_ID:......, SIGNAL_LEVEL:RED
? or i should do something else?
Why there is zero-lenght line segment in 4-th test? 1st question: no comments, as know. Reread a problem.
2nd question: no comments. Reread a problem.
3rd question: i think it isn't print, because we haven't event "signal lost" and may still assume what cell is same
4th question: no comments. Reread a problem.
...
My 6th question: should i use ( char * ) instead off ( unsigned char * ) or vise versa for names? I disagree with you, Fly.
Question 1 - indeed, seems like we should choose the stronger signal, not the best color, but indicator is only able to distinguish between colors, not strengths, so it's a bit unclear.
The answer to question 2 depends on what happends if distance is equal to critical.
Take a look:
1. "If the distance between the phone and a base station is less then a certain value, then the signal is ideal"
2. "If the phone is moved away from a base station further than the threshold distance, then the indicator goes indigo, then blue, green, and so on"
3. "Rc is its threshold distance within which the station's signal is shown by the violet color of the indicator"
These three statements can't be resolved clearly, IMHO. "within" means <=, while "less" means <.
As for question 4, it isn't really clear, because "The phone stays connected to the same station until its signal goes red; then it switches to the search mode and tries to select a new station", so we can't tell whether the phone is in search mode from the very beginning or no. Although this doesn't seem to affect our output, behaviour is poorly described for this problem. Questio #1. I don't know. I tried both and got WA#8.
Question #2. "If the distance between the phone and a base station is less then a certain value, then the signal is ideal".I think its right. "within which" means such as "inside which".
Question #4. "When the phone is being turned on, it selects a station with the strongest signal. If there are several such stations, then the station with the minimal (with respect to the lexicographic order) name of the cell is selected among them." Color isn't take to account.
Edited by author 26.11.2005 20:12 Question #2.
<= get WA #6
< get WA #8 I agree to *answers* to your questions, but I disagree with reasons.
Indeed, your answers are correct and I got them as well by experimenting. What I claim to be wrong is uncertainty in problem statement; such details should be pointed out. It probably can be extrapolated from this phrase "Violet corresponds to the strongest signal". But then it turns out that the 1st picked station can be violet only (also _strongest_ signal), and if there is no violet station nearby, it's undefined behavior :D There's the line: "Also, we assume that at the points where the segments join, Shpuntik's phone never changed cells and that for each of the stations the curves of change of the signal's level do not pass through these points." in description.
I got wa on 4. And after putting this line to judge whether it suffers the condition above:
if (case_is_wrong) then DIE
I got RE on 3. I think at least case 3 is wrong, or the description is wrong!
Edited by author 01.11.2005 14:46 If I am not mistaken, base station selection is made ONLY when power indicator shows RED. Otherwise we stay connected to currently selected base station (until power indicator gets RED) even if there is another one with stronger signal. i means, while changing channel, which one should be chosen:
if there are two stations providing very strong signal, but the SAME COLOR. i should choose the closer one or according to their names.
in other words, i should choose according to the DISTANCE, or the COLOR of stations? | | How to solve this problem? (-) | Alexey | 1174. Weird Permutations | 31 Aug 2008 06:44 | 3 | You should find something interesting in the list of permutations which their program gives to you. ) | | WA#24....Please help me... | rohit | 1430. Crime and Punishment | 31 Aug 2008 06:02 | 3 | Please tell me what is test..I m stuck at this problem for long time. Guys...please tell me..I am sure my algo is correct. Maybe overflow? I use int64 everywhere. | | Very easy problem) | Quiet WOLF | 1162. Currency Exchange | 30 Aug 2008 23:31 | 3 | Write Bellman-Ford.
And receive AC :) This problem can easily be solved by DFS in 0.001 time. I also think that there are several other ways to get AC. But looking at the forum, it seems that there is only one correct solution by Bellman-Ford algo. It is disappointing statement No, I've solved it just with DP with some optimizations to avoid TLE... | | No subject | 107th | 1479. Scheduled Checking | 30 Aug 2008 17:31 | 1 |
Edited by author 31.08.2008 10:59 | | CRAZY | And IV | 1108. Heritage | 30 Aug 2008 12:35 | 2 | CRAZY And IV 11 Jul 2007 15:22 for 17
101947476276204101728256649522401828167927212018620660601704890929001825509713\
523503992610358334066272592383395838866387684206587940612931467354271617915520\
937995552021084248226726638101995425579805732299965812369024137733196293515624\
424016917925247649882464052696187736119522132640993696042743480414771264544528\
304342996477011745452606136325735302189423673044792743354919189308823448247968\
364421235334689505731269305763052451307463747806343113812624926109241630690221\
319433572220844418278565182710065248974135752363837484684227814042631918627155\
461779101734021597624242710578359837429955380225996920358684927211301458328724\
872971117350243844049604206441001676118134664338476015421798968307893538522879\
738221475097682927759727395878448090218721802381455630439305830088798521845679\
481860616779484116388947412631032214162894648924320167381731382043760565596316\
369583724745469072297566662773233839980675859313837171769862327336088652054094\
267810251588071940758900455743286020948251380733842671672740944609550580767140\
732173862408107529498531326164067492981649810743591794028985785355587051520395\
534630526455902456336065991163514533196314608519640788565818155174136944051021\
402419912329933809924219549508467344366233051463150285255689476642468105302211\
129811175620821751513860525253757739561042423044403448246267339558656517317865\
002657449204595579742675299432398952884881848630853237246246329746536660490193\
464231004280212833182760067389817797704719330912736030371597912626318279787464\
408039560242064494924683367742401523278572128169942111951355492148915513062977\
767559605391394475240035421689924596879829323560599623881796417132645355452834\
213394295243124161077956028677251502132801495011896740549214977611725577583592\
694131902274214479285847997219514083715777380237852141555799465598015245152196\
197540850796658589527188879862044709016545796583701795889195497514304242690490\
020048282090997220570151819282983750070905128662528860703021805696428045708735\
217070342408403948629748287182302572655831689847248362835661078053350461256021\
547252746204855622282300021449560142568349748618704900105957291367569310068046\
468168740774195170563917695384082803306556375506007071106140974657491081051319\
628733980823861151213743575371668595999162366202372771193718906231527267750197\
486208221400172590739690964186859083713098418413904193544036347981505565030074\
358430960182277688743565437791001750095814547355349908834277382701916967194842\
245938118072198823848678058047817857919108391286687178444965713477577691631264\
683265079619859936065323962869265275426820111891855142296804948531343541948140\
233325861685585654210886918693438429463852147233236461744139070486591334508296\
457638112829900981331742227600028166778501177206627837766424230432751776092660\
905333207273480471338084952622102287953496875636006963328797863179813674926308\
972179356464333251094493151732499958616350679087178949479216828756235540404960\
713180088292868461069552267966556582868379454800273376303872247435830687267393\
790632637291832475998713420228193860684332834272020209787394749585310693327423\
238069146069235258021192858102358746511372078580637116458067121739895510040929\
701669398478973873849065653363239219214902435330524238782375642808353026188773\
975983490697280154677778905491647471081200979748252065741117416477107374679345\
743129808520178057105601496774507566188669824677145600348843302843159620546174\
334832342261955415164552484365573829013677168443541042252294869025362302975188\
357843863352803540278804875258862826997522470901969159918254181349566887374862\
780691547981769474082634729847029564231178299643587820218295909268066469439209\
361491238062665635552348001777523991902386442621767153531136625588050180493206\
062242422931907554959039295465983742398584740169266919842721984484510373349152\
245952678807152410758717023226165898261554089953972142911218163641942164495520\
363355981591449370142813000605247823024169443289315723858776805353395074747315\
965280001341580608595769985570739736089162750132694522089916488924640668733155\
223160937927062251627103706892028018658869521523347072156904472183243404821906\
304272096715336825846963200847460589163253872114645787381529273086086455786566\
275126829436164942555105137673574243094665153514651721735923240573324863824143\
359851248308716379355679879591213016511440586376295006227271629274118951942116\
109405534002079180597499184909932263968054958258105257514955012091459820800057\
750331964913568287731523210748968398312957273480719457275559998248560139266250\
842179935854173511566613222948421881382475426284893241966842479917946517496740\
184005176543418886207284298477461122754701546519893184842702869621306705911094\
049863539818995805682571658767661717581202478037805775168469748014496159567653\
867547996292165520326070898580254978876493271964884556400923688543210364055051\
615791042268351757817686013185351170250274124497224412719348764846625708068905\
347316664552317520539285800977782965249223808291145291897524324064574143276004\
109309312489603647534696923445636909725936822586274552277423207555843177718296\
952141969023679154209897246157142828813380353736229450306049855932736418036398\
961065760057909708160303588848920437271046591207676445275229419800540502365601\
287894038341619051056594181736631833907096742273385627262684929705142348821715\
717757958905859254479917848700048385072249130142420650970420023287836827630391\
269918643914897622117657803662758429145580464113366704590130560966336742522948\
426614878287442493127007876368649283731064173754397064710293902186485691882881\
716468262176381143462572160900086704950634329551688625081703810335385515304188\
304427279243385438689682372007527042313863650071970451630047737592261712679997\
032408347081035265513334702499006133711987239421535054848463109822318586991438\
551922502617715683296404173690528506176471786187891982050545166477348649137207\
858429882060978569493345683444105018762245149581702579220458862325192666588097\
882057919708196676295001981428692007892030715958615319031669962717200873646950\
008362407507959942578561644410507683474807389207851292100875691409227155727299\
364582623223275295062939276067857778361135380509202853919256414424503014505002\
381304252092914928928657140629156647824122226663231270929114949838133512858284\
553659329483020863495070396992270655333530795534599510106923678406707717858463\
733321785627940852507792509130884345783566091608572106334515971552960334058748\
839064383371028242595100897586460484856407787378736322494137454900025766401953\
432343390997934836648888471475774056788466362851920363702646297700862884419541\
987571882177506168821922809933537205416312245942012156034442836293522503739936\
065901336541052522501549407560959605649286737153302742922152520560377209508086\
113982015028412372790811903863008802363619805248367847394429412199369638423963\
346257500612817015824336492312600977669312112774203566434781934594072293770110\
076734956699178075515846558405491752217839681661596291831016443991991412071772\
137912039918597306162686225588910504498519604052700515641172600244195414239780\
360630322446478496281792974758878314317259627986710759191054660959328452748938\
311478199535939071913360744286895873622646699721551825987559522917879477445778\
382908124421543471646833635556615676388512579824507455359252651958896902958855\
668692843421836979526955093577635147345988824158949081202382108767126209821958\
442260208948449410343769646095764053362538731014265928873692318388291223942552\
421374501833810037541831933487375710124093270523976456909327768504943218645340\
607609285579343097200825103534646400864178642528922574211254451904465997353464\
510210512105006920359247962529839263726973406559916187064671120861970908188292\
868899774538386530986348457725714314783858497404840192981602404268584138070725\
841997724622331835018556950009953063992884998005153946253938533541281660071091\
429424514187229202508780169660518187519401276672888317734775745997919858219524\
239671755968351481290456477508563245546726259397317514968395897774994941937641\
857833929270815117032962881367672472733333474420273123621265406470085013468333\
119658823407066792641139759838451752805070829259243717167818624584861840639371\
799738640140902077418451591486238742100062761371526700751326999370092318078314\
368489806490770522093379075525353121672988587838215010713807872451131794229812\
571740806401522059317899185264121384303947536112199986762810620846685091274271\
916661463411839224984962435729012932133343175807034982705801566084727334333517\
750351634518081659225254828123214035942931842340124701666219235091380967050219\
134380278144223506076120089021003305258960092049465404548159621409475037953312\
173078114622050941210429800533486071767071202411442403056916088204245448279934\
704578107634786938798517235147720543138315118953409306950329781338209463889377\
470710968341797194581860416354750881171100231404610379962003554616111671902862\
697124103504073629731011619138818833069834499687213768467359661901421300332751\
135267231414560709815668898412329407691576395889529755528790383487960697775451\
764038654169029787737935618427828193963614002421796514377717795463593318199322\
955753836683147459314864427699947923397123162519743718033336537904778738909605\
637535529913079411797144286416514371413616596779207789988278478924015088300574\
620331274640498180855093038975080909740589748091444091955495089168886894992931\
722766013965335478296019734869490910635590720643080340322002266437052736851404\
370448578218773247775710274843449000512256418836859647205346520886692955706538\
390045352933459827863586330492444094263842446831131327801920868587368676765127\
464799206582996201527957193631845220731936291769995842530852430364383423166599\
679992975649367769381074666316737598564092830628272038204585425201246620334489\
400821894768076677303753945731268505937331250013826162664602013860213628505438\
613088614606018479330817153878987155118618609687453530431653387882068520150477\
956100336516235868097480522775325784653682625830314869032172517939835171315827\
527818656693744191724828177518601488616783147760717381768688995404385410128790\
806080374638954228188788965293885694114845059354594141324091298839591528017533\
374376909034613941653796919310036371349410974127680808733282647443187903534964\
642131308935682424358670417681693542973321116904594079146133429407276088733945\
898033202097039338159676498549164777673752492328509349038688744456934749959878\
258115431677204583992640922080230035273300812851769756693954561073535941385671\
779980272011075384337721741933458261162553735568314260381570179840749330416564\
616138089504727323977641731169447353392419772273507504583381222900280346430609\
668801170796983251907041738862982742733739119007927215655537267575350108342329\
731081927263234354309447041595207150072369177349725163439778171878237027628984\
333053910381856127025724485995310690236572281053312911768824281104255667731327\
736458715008245966424251295625486976554262285167088557534827179182711225022332\
845222610193710107652038966100641295486691349710311830287284272469727839643508\
946955974388642039006053186406508749446240835991794524254394068907649064544452\
350242828197100347491166053166607446120481569385325342398012306741905199958390\
128295206683964040549289874988771568591787120902315278985275898941333362328422\
266369156347284504772554552506206951479068139196600874413295479414473418725240\
107208106596031566745371724243015265899349651563027222546179832138183186377082\
715966183438825270051206480864418998224084738692973627100636535354403693980897\
627795927225862076213309855053657925340504647080855990490604097983768359676020\
237508751128068071367571958957906787792366376078741525473958355866250698725299\
401727299234522457850902882394018752173543794479867862490304338035339553949480\
533652250079630747366148838542635928380062014110986183591526646807726525104184\
827063578382720829337894312562609400025648517428941403830758729200703182792813\
354385027899116087085610304706934512867480416613355379821893749723434880657907\
554203214056693702832236842657009096050756966707760262570104538244439768550998\
803621573944751131417524487370379997581423292608026951132955215726736195305524\
500008028004278241580124445172672845856833559303763883412738078735403012875435\
196438724201435550629314003242865871060459174526037526146069010986769814990479\
943640765942659527630905623713437127333041857359589077454949500166841617658178\
497257881864153377674716536605247720987938913725824327968170828620767315494360\
803994257127167979564613665895891374659799355444426493030394805401402462310282\
893819382701745421701555881725229367682313142125324323315200674528018932739836\
808896328648138573883303088450220616118017085196397999206172414294846638520478\
439013164544032387576566903465885352798453222311399382356831803583763409801338\
783777117184879285557880853209634110451074793500334384861799435547383606869245\
365875167216703128980893926597268388841854917396424738722231710181510123192620\
547842731837553604377204489437125790621726819914691642640604036927915509764408\
638948576290607782570194036590190058645888660696214150709897480692517189975771\
382406186742388147227908175336823422378979858400616087580384418863441649637944\
184584180656828304016631806032427311596287322544908429516198672707778430371394\
990050485057523131032041168620610716240871714017424485591690725187211238174477\
830719311581218217414248803834188552501147223451149926063565937553975663259909\
054515083809899259881445992853611185649260234526169552619316248945216272787187\
821466608617856311968660449514151206062953427830249813010159032237499601291295\
807
THere are not enough space on the A4sheet of paper )))))))))))))))))))))))))))
Edited by author 11.07.2007 15:28 Re: CRAZY Dmitry "Logam" Kobelev [TSOGU] 30 Aug 2008 12:35 I have exactly the same answer for n = 17. But stil wa. Is the answer for n = 18 begins from 103932879... and ends with ...884485443, having 26681 digits?
Edited by author 30.08.2008 12:35 | | how to | nttjuvwamsncc | 1520. Empire Strikes Back | 30 Aug 2008 05:41 | 3 | how to nttjuvwamsncc 14 Feb 2007 14:35 I think that enough for each circle-boundary to be
covered by others circles
or we have covering problem of arc by given set of arcs.
Have Ac based on this idea.
1504 ac with the same idea but
many hard work with eps.
Main difficult moment:
ends of arcs computed with help of arcos
have error with respect to exact values and may be
greater or smaller of them , but exact values of boundaries of intervals lies in distance eps=1.e-16 from computed values.
Edited by author 22.03.2008 17:50 It's Vorony diagrams problem. Of course, you may solve it via covering all arcs of all circles or even try binary search on radius.
2svr: as for comparing arcs - why do you need angles? Just keep x/y pairs defining direction and compare these pairs for <, =, > of angles they define. One of easy easy ways to do that:
y>0 || y==0 && x>0 - 1st part [0;pi)
y<0 || y==0 && x<0 - 2nd part [pi;2pi)
if 2 vectors belong to different parts, you alredy know which angle is smaller. If not, check sign of their cross product. | | What's the "good" algo for this problem | Todor Tsonkov | 1469. No Smoking! | 30 Aug 2008 04:41 | 12 | I coded for 10 minutes brute force which got TL on test 4.. any ideas about the "good" algo ? Haha :) Some more hints ;) You can implement stuff, described in Cormen, easily, using set. That's what I was trying to say.
Ilya Razenshteyn. There is obvious "slide line" algo, that can be applied in O(NlogN). But there is a little problem here: perpendicular to ox line segments... It's not problem! I don't exam this case and got AC.
Can you explain a little more about this algo ? This isn't problem too. Just rotate all points by the constant angle.
const
angle=pi/60;
var
x,y,buf1,buf2:real;
begin
...
Buf1:=x;
Buf2:=y;
x:=Buf1*cos(angle)-Buf2*sin(angle);
y:=Buf1*sin(angle)+Buf2*cos(angle);
Edited by author 01.04.2007 16:14 I solved for me the little problem of vertical segments by
applying affine matrix
[2 3]
[5 -7]
or any other to given coordinates.
As result algo from Cormen can be taken without any changes.
Edited by author 13.07.2007 17:09 As far as me, I used some my heuristics with vertical segments:
First, when reading points i makred point with lesser x cordinate as enter point.
I sorted points by X, and if X are eual then sorted by enter mark.
This assumes then enterpoint will be before exitpoint of segment in set. Vertical segments are easy to treat. Just sort X ascendingly and for equal X sort Y ascendingly. When you add vertical segment, consider its topmost Y coordinate during comparisons, and when you add some other segment, assume equality when its scan-line ordinate is compared to that one of vertical segment in the set.
Such behavior is identical to the one we'd apply to the segments set after rotating it for small enough angle. Another way to see that - apply skew affine transform
x2 = x+y*1e-6
y2 = y
and see how formerly vertical segments are handled in this case.
Edited by author 30.08.2008 04:52 | | Ошибка в условии | Piratek-(akaDK) | 1291. Gear-wheels | 29 Aug 2008 18:32 | 2 | Последняя строка входа содержит два числа: номер шестерни, соединенной с кинетическим генератором и скорость V (1 <= V <= 1000), с которой она вертится. Скорость может быть как положительной, тогда считается, что шестерня крутится против хода часовой стрелки, так и отрицательной, тогда считается, что шестерня крутится по ходу часовой стрелки. - Получается, что шестерня первая крутится всегда против часовой стрелки! | | Let's talk | Igor E. Tuphanov | 1429. Biscuits | 29 Aug 2008 18:13 | 6 | Why there is so large discussion about easy problems and so few about interesting ones?
FE, let's talk about floating point arifmetics. Did you maid eps (very small 'soft' constant) to 'soft' your calcualtions? What value of your constant? I made it 1e-12 - it vas too small, even 1e-8 was too hard. But with 1e-6 everything was O'Key. So far I have WA13 and tried 1e-6, 1e-8 and 1e-10. All give WA13.
There is a test nearby in this forum:
2
0 0 10000
9999 0 1
Edited by author 29.08.2008 16:22 Re: Let's talk Vedernikoff Sergey (HSE: EconomicsForever!) 29 Aug 2008 13:36 All the calculations can be done with exact arithmetics - you have integer numbers in the input! I doubt integer solution is possible under given TL/ML. And 1e-8 is enough to solve the problem using double.
Edited by author 29.08.2008 18:14 I have a question - is WA13 about precision or not? Finally got it!!! :) WA13 is about coinciding circles, they requied different handling... | | determinant | Alias aka Alexander Prudaev | 1627. Join | 29 Aug 2008 17:17 | 1 | determinant Alias aka Alexander Prudaev 29 Aug 2008 17:17 How to calculate Determinant without BigInteger ? | | Reading in C# (+) | AlMag | 1002. Phone Numbers | 29 Aug 2008 15:34 | 1 | How should i read data in C#? Cuz i have Crash 3 :(
Edited by author 29.08.2008 15:35 | | Be careful! | Sandro (USU) | 1429. Biscuits | 29 Aug 2008 14:54 | 6 | Remember that two cuts can coincide. One more hint:
Test:
2
0 0 10000
9999 1 1
Answer:
4
Edited by author 29.08.2008 16:23 Re: Be careful! Vedernikoff Sergey (HSE: EconomicsForever!) 29 Aug 2008 13:59 Answer is indeed 4. Analyze sample carefully. Sory, I checked it for 9999 0 1 :) For 9999 1 1 the answer is 4. |
|
|
