Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

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

ورودی

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

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

در n1 سطر بعد، نیمه‌ی پایین ماتریسی قرار دارد که فاصله‌ی پاره‌خط‌ها را در مختص z مشخص می‌کند. اگر در سطر i1 ام از این مثلث، j امین عدد را dij بنامیم (i>j)، به این معنی است که در نقطه‌ی تقاطع دو پاره‌خط i و j در صفحه‌ی xy، داریم: zi=zj+dij. اگر dij=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

ابزار صفحه