חידת המלבן המינימלי

בימים אלה מתחילה תחרות ליגת התכנות לתיכונים 2012/13 (High School Programming League). לרוע המזל, אף על פי שאין מניעה עקרונית או טכנית, נראה שגם הפעם אין ייצוג ישראלי בתחרות המקוונת הזו, שלמרות שמה פתוחה למעשה למתחרים מכל הגילאים ומכל רחבי העולם.

אחד ממארגני התחרות הוא ידידי-דרך-האינטרנט, פרופ' לוקאש קושנר מהאוניברסיטה הטכנולוגית של גדנסק, שהוא גם מהאחראים לפרויקט הקומפיילר המקוון ideone.com (שכתבתי עליו כאן). באישורו של לוקאש, בחרתי להביא לכם חידת תכנות אחת מתוך התחרות. הרמה היא של הסבב הראשון בלבד, רק כדי שתבינו על מה מדובר. אם בא לכם להשחיז את כישורי התכנות, או להסיר מהם חלודה, זו ההזדמנות – ואם תמהרו תוכלו גם להספיק להירשם לתחרות (ההרשמה נסגרת ב-5 באוקטובר). המטרה היא לכתוב תוכנית שלמה, בכל שפה שתבחרו, שתקבל קלט ותפיק פלט בהתאם לפירוט. בהצלחה!

בעיית המלבן התוחם המינימלי

חשבו את המלבן התוחם המינימלי שמקיף אוסף נתון של אובייקטים דו-ממדיים. כלומר, מלבן מיושר לפי הצירים שמכיל את כל האובייקטים שצוינו,  והוא בעל השטח המינימלי מבין כל המלבנים שמקיימים דרישות אלה.

הקלט

ראשית, תקבלו את הערך t (קטן מ-100), שהוא מספר המקרים לבדיקה.

כל מקרה מתחיל בערך מספרי שלם n (קטן מ-100) – מספר האובייקטים באוסף. n השורות הבאות בקלט הן התיאורים של האובייקטים עצמם. כל אובייקט מתואר באמצעות תו אחד ומספר פרמטרים:

  • נקודה: p x y (לפי הסדר משמאל לימין), כאשר x ו-y הם קואורדינטות של נקודה.
  • עיגול: c x y r, כאשר x ו-y הם קואורדינטות מרכז העיגול, ו-r הוא הרדיוס שלו.
  • קטע קו: l x1 y1 x2 y2, כאשר xi ו-yi הם הקואורדינטות של קצה i של הקטע.

בין מקרה בדיקה אחד לאחר מפרידה  שורה ריקה.

הפלט

עבור כל אחד ממקרי הבדיקה, יש להוציא כפלט ארבעה מספרים – הקואורדינטות של שתי הנקודות שמייצגות את הפינה התחתונה השמאלית והעליונה הימנית של המלבן המינימלי, לפי סדר זה: קואורדינטת ה-x של הפינה השמאלית התחתונה, אחריה קואורדינטת y של הפינה השמאלית התחתונה, קואורדינטת x של הפינה הימנית העליונה ולסיום קואורדינטת y של הפינה הימנית העליונה.

אפשר להניח שכל הפרמטרים של האובייקטים הם מספרים שלמים, ושכולם תחומים בהכרח בתוך מלבן שמשתרע בין 1000- ל-1000 בכל אחד משני הצירים.

דוגמה

קלט:
3
1
p 3 3

2
c 10 10 20
c 20 20 10

1
l 0 0 100 20

פלט:
3 3 3 3
-10 -10 30 30
0 0 100 20

קדימה, לעבודה! 🙂

להרשמה
הודע לי על
8 תגובות
מהכי חדשה
מהכי ישנה לפי הצבעות
Inline Feedbacks
הראה את כל התגובות

מישהו ניסה לפתור את החידות האחרות? אני עבדתי הרבה על השלישית, עם העצרת, ולא הצלחתי. החישובים פשוט לא עובדים, בכל טיפוס משתנים שניסיתי לעבוד איתו. גם עם BigInteger ו-BigDecimal (בג'אווה), אני מאבד חלק מהמידע.

שלום. הייתי שמח לדעת מהי מסגרת הזמן לשאלה כזו ובאיזו שפה כותבים את הקוד. בכל מקרה הנה הפתרון שלי בפייתון (לקח כשעה לתכנת) ****** אזהרת ספויילר ******* class Shape: def __init__(self, params): self.params = params class Circle(Shape): def get(self): x,y,r = self.params return (x+r, y+r), (x-r, y-r) class Line(Shape): def get(self): x1, y1, x2, y2 = self.params return (max(x1,x2), max(y1,y2)), (min(x1,x2), min(y1,y2)) class Point(Shape): def get(self): x,y = self.params return (x,y),(x,y) def parse(): f = open(r'c:\temp\input', 'r') t = int(f.readline()) res = [] for _ in range(t): prob = [] n = int(f.readline()) for _ in range(n): arr = f.readline().split('… לקרוא עוד »

סיימתי 🙂
הפלט אצלך רשום מימין לשמאל.

***אזהרת ספוילר!***
בכל מקרה אני מאתחל את הפינה השמאלית התחתונה להיות הימנית העליונה, ואת הימנית העליונה להיות השמאלית התחתונה, ואז עבור כל צורה אני משנה את הקואורדינטות בעת הצורך. למשל, קואורדינטת ה-X של הפינה הימנית העליונה תהיה הערך הגדול מתוך הערך הקודם, וקואורדינטת ה-X של הפינה הימנית העליונה של הצורה הנוכחית. במקרה של קטע (L), יש לבדוק את שתי הפינות של הצורה.

כרגיל, פוסט מצויין ומעניין!!!
אהבתי את התרגיל הנחמד, יצירתי ביותר.

תודה על המידע על התחרות, מעולם לא שמעתי עליה…
מקווה לעוד חידושים רבים 🙂