ყუთი სათამაშოებისათვის

დროის ლიმიტი: 3 წმ

მეხსიერების ლიმიტი: 512 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: IBSU, 2015, ზამთრის ოლიმპიადა, XI-XII


ცოტნეს მოსწყინდა ძველი სათამაშოებით თამაში და მშობლებს ახლების ყიდვა სთხოვა. მათაც გადაწყვიტეს, მისთვის სურვილი შეესრულებინათ და მეორე დღეს მთელი ოჯახით სათამაშოების მაღაზიას მიაშურეს.

            მაღაზიაში სულ N რაოდენობის ახალი სათამაშო იყიდება და, რაც არ უნდა უცნაური იყოს, ყველა მათგანს ბრტყელი ამოზნექილი მრავალკუთხედის ფორმა აქვს (სათამაშოები ასევე ბრტყელ ყუთებში ძევს, რომელთაც გააჩნიათ სიგრძე და სიმაღლე, ხოლო სიგანე, შეგვიძლია ჩავთვალოთ, რომ არა აქვთ). მამამ ცოტნეს განუცხადა, რომ ამჯერად მხოლოდ ორ ახალ სათამაშოს უყიდდა და მანაც გონებაში მაშინვე დაიწყო ვარიანტების გადარჩევა, მაგრამ მიხვდა, რომ ისინი ძალიან ბევრი იყო. ამიტომ, გადაწყვიტა სათამაშოთა წყვილების შერჩევის მხოლოდ Q რაოდენობის ვარიანტზე შეჩერებულიყო.

            ცნობისმოყვარე ცოტნემ მაშინვე დაიწყო ფიქრი შესაძენი სათამაშოების შეფუთვის დეტალებზე. კერძოდ, ყოველი მისთვის საინტერესო სათამაშოთა  i,j  წყვილისთვის მას სურს შემდეგი ოპერაციების შესრულება:  თავიდან ორივე სათამაშო ძევს თავის ბრტყელ მართკუთხა ყუთში (ისე, როგორც ზემოთ არის აღწერილი) და მჭიდროდ ებჯინება მის კედლებს. ცოტნე დგამს ამ ორ ყუთს მაგიდაზე ერთმანეთის გვერდით (i-ური სათამაშო შეიძლება დაიდოს j-ურის როგორც მარცხნივ, ასევე მარჯვნივ), სათამაშოებს აცილებს ყუთებს, მიაჩოჩებს მათ ერთმანეთისაკენ რამდენადაც ეს შესაძლებელია (ისე, რომ ისინი ერთ სიბრტყეში დარჩნენ და ერთმანეთს ებჯინებოდნენ) და მიღებულ კონფიგურაციას კვლავ ათავსებს ახალ ყუთში (სხვადასხვა ზომის ცარიელ ყუთებს მაღაზია მას უხვად სთავაზობს). რადგანაც ცოტნეს, ასაკის მიუხედავდ, უკვე ახასიათებს პრობლემათა ოპტიმალურად გადაჭრისაკენ სწრაფვა, მას აინტერესებს ახალი ყუთის ზომები. მაგიდაზე დადებული სათამაშოების მისი ზედაპირის პარალელურად მოძრაობით ახალი ყუთის სიმაღლეზე გავლენის მოხდენა შეუძლებელია (იხილეთ ნახაზი ქვემოთ). ასე, რომ ცოტნეს სინამდვილეში ამ ყუთის მხოლოდ მინიმალური შესაძლებელი სიგრძე აინტერესებს.

            დაწერეთ შესაბამისი პროგრამა და დაეხმარეთ მას ამის დადგენაში.

            კიდევ ერთხელ მიაქციეთ ყურადღება იმას, რომ სათამაშოები შეიძლება ვამოძრავოთ მხოლოდ მაგიდის სიბრტყის პარალელურად, მათი რაიმე სახით მობრუნება დაუშვებელია. ამგვარად, ამოცანა შეიძლება განვიხილოთ, როგორც ორგანზომილებიანი: Ox ღერძი ემთხვევა მაგიდის ზედაპირს, ხოლო Oy ღერძი, რომლის გასწვრივაც იზომება სათამაშოების და ყუთების სიმაღლეები, მაგიდის ზედაპირის მართობულია. ყუთების გვერდები კოორდინატთა ღერძების პარალელურია. სათამაშოები საკმაოდ უცნაურია და მათ შეუძლიათ ერთ წვეროზეც კი წაუქცევლად „იდგნენ“ მაგიდაზე (ამოცანის პირობის უკეთესად გასაგებად ყურადღებით გაეცანით ილუსტრირებულ მაგალითს).

            შესატანი მონაცემები: სტანდარტული შეტანის პირველ სტრიქონში მოცემულია ერთი   მთელი დადებითი N რიცხვი (1≤N≤100 000) სათამაშოების რაოდენობა. მომდევნო N რაოდენობის სტრიქონი შეიცავს ამოზნექილი მრავალკუთხედების აღწერას შემდეგი ფორმატით: თავიდან მოცემულია ერთი ნატურალური km რიცხვი (3≤km300 000) - წვეროების რაოდენობა m-ურ მრავალკუთხედში. შემდეგ მოდის km რაოდენობის სტრიქონი, რომელთაგან თითოეულში ჩაწერილია  xm,s, ym,s რიცხვთა წყვილი (თითოეული მათგანის აბსოლუტური მნიშვნელობა არ აღემატება 109-ს) - m-ური მრავალკუთხედის წვეროების კოორდინატები საათის ისრის მოძრაობის საწინააღმდეგო მიმართულებით, მოცემული მისი შესაბამისი იმ ყუთის კოორდინატთა სისტემაში, რომელიც მაგიდაზე დგას (ეს ნიშნავს, რომ ym,s≥0 და, აგრეთვე, ყველა სათამაშოსათვის არსებობს ისეთი vm წვერო, რომლისთვისაც    ym,vm=0). ყველა km-ის ჯამი (აღვნიშნოთ იგი S-ით) არ აღემატება 300 000-ს.

შემდეგ სტრიქონში ჩაწერილია ერთი ნატურალური Q რიცხვი (1≤Q≤500 000) - ვარიანტების რაოდენობა. მომდევნო Q რაოდენობის სტრიქონიდან თითოეული შეიცავს it, jt ნატურალურ რიცხვთა წყვილს (1≤it<jt≤N) - სათამაშოების ნომრებს მორიგ ვარიანტში.

შეტანის სტრიქონებში მონაცემები ერთმანეთისაგან თითო ჰარითაა გამოყოფილი.

 

გამოსატანი მონაცემები: სტანდარტულ გამოტანაში უნდა გამოიტანოთ Q რაოდენობის სტრიქონი. რომელთაგან თითოეულში უნდა ჩაიწეროს ერთი ნამდვილი რიცხვი -  ახალი ყუთის მინიმალური სიგრძე სათამაშოების წყვილთა შერჩევის მორიგი ვარიანტისათვის. პასუხი სწორად ჩაითვლება, თუ ყველა რიცხვი გამოთვლილი იქნება აბსოლუტური ან ფარდობითი ცდომილებით არაუმეტეს 10-9.

 




მაგალითები

შესატანი მონაცემები
2 5 0 0 4 2 6 6 3 8 -2 4 5 0 0 2 0 8 4 5 11 3 12 1 1 2 დაკოპირება
გამოსატანი მონაცემები
14.5000000000 დაკოპირება