المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۳:سوال ۸

سایه‌ی پاره‌خط‌ها

تعدادی $(n)$ پاره‌خط در فضای سه‌بعدی داریم که مختصات دو سرشان صحیح است. تصویر این پاره‌خط‌ها بر صفحه‌ی $x,y$ به ما داده شده است. فرض کنید که تصویر هر پاره‌خط نیز خود یک پاره‌خط است و هیچ سه تصویری از یک نقطه عبور نمی‌کنند. به ازای هر دو پاره‌خط که هم‌دیگر را قطع می‌کنند، اختلاف مختص $z$ آن‌ها را در محل تقاطع نیز می‌دانیم، هم‌چنین می‌دانیم کهدام یک بالاتر است.

برنامه‌ای بنویسید که با اطلاعات فوق، یک سری مختص $z$ برای دو سر پاره‌خط‌ها تولید کند، طوری که شرایط بالا برقرار بماند.

ورودی

در سطراول ورودی عدد $n$ که بین ۲ و ۲۰۰ قرار دارد.

در $n$ سطر بعد، به ترتیب مختصات $x$ و $y$ دو سر پاره‌خط‌ها قرار دارند.

در $n-1$ سطر بعد، نیمه‌ی پایین ماتریسی قرار دارد که فاصله‌ی پاره‌خط‌ها را در مختص $z$ مشخص می‌کند. اگر در سطر $i-1$ ام از این مثلث، $j$ امین عدد را $d_{ij}$ بنامیم $(i>j)$، به این معنی است که در نقطه‌ی تقاطع دو پاره‌خط $i$ و $j$ در صفحه‌ی $xy$، داریم: $z_i=z_j+d_{ij}$. اگر $d_{ij}=0$ باشد یعنی تصویر این دو پاره‌خط هم‌دیگر را قطع نمی‌کنند.

خروجی

در فایل خروجی، در سطر $i$‌ ام از $n$ سطر، مختص $z$ دو سر پاره‌خط $i$ ام را بنویسید. مسئله بیش از یک جواب دارد، یافتن یک جواب کافی است.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4
10 10 10 17
9 12 13 12
11 13 11 8
12 11 8 11
4.1
0 1
-4.7 0 2.5
0 7
5 9
-2 -6
1 -9

ابزار صفحه