فهرست مندرجات
چند ضلعی
یکی از دوستان به تازگی یاد گرفته که برنامه‌های هندسه‌ی محاسباتی بنویسد: مساحت شکل رو حساب می‌کند و تشخیص می‌دهد که آیا نقطه‌ای درون یک چند ضلعی محدب هست یا خیر و از این دست.
عمو شایان به این دوست ما می‌گوید: «اگر راست میگی، برای چندضلعی‌های غیر محدب این کار رو بکن!» این دوست ما هم عوض سرخورده شدن، ادعا می‌کند که می‌تواند با زمان کم‌تر از خطی مسئله را حل کند. فقط یک مشکل کوچک وجود دارد: ورودی مسئله $n$ تا نقطه‌ی چند ضلعی را شامل می‌شود که خوب خواندنش کار را خراب می‌کند. عمو شایان هم با توجه به سخاوتش، برای این که جای پیش‌رفت به این جوان آینده‌دار بدهد، امکاناتی را فراهم می‌کند که دوست ما بتواند ادعای خودش را ثابت کند. دوست ما بایستی از عمو شایان مختصات بعضی رئوس چندضلعی را پرسیده و در نهایت تعیین کند که آیا نقطه‌ی مورد نظر «درون» یا «برون» چندضلعی جای می‌گیرد.
برنامه‌ای بنویسید که:
- تعداد رئوس و مختصات راس اصلی را از کتاب‌خانه‌ی پیوندی بخواند.
- مختصات تعداد کمی از رئوس را از کتاب‌خانه‌ی پیوندی بگیرد.
- پاسخ را به کتاب‌خانه‌ی پیوندی اعلام کند.
کتاب‌خانه
توابع زیر در کتاب‌خانه یافت می‌شود:
()Init این تابع باید دقیقا یک بار و پیش از هرگونه تعاملی با کتاب‌خانه فرا خوانده شود. تعداد رئوس چند ضلعی، $3\leq n \leq 1000$، را باز می‌گرداند.
()get-query مختصات راس اصلی (همان راسی که باید وضعیتش را مشخص کنید) را به شما می‌دهد.
(get-vertex(index مختصات راس شماره‌ی index از چندضلعی را در اختیارتان می‌گذارد. رئوس چندضلعی به ترتیب ساعت‌گرد و با شماره‌های ۱ تا $n$ مشخص می‌شوند. دقت کنید که قدر مطلق مختصه‌های رئوس چندضلعی و نیز راس اصل از $10^8$ بیش‌تر نمی‌باشد.
(Report(status با فراخوانی این تابع می‌توانید پاسخ خود را به کتاب‌خانه تحویل دهید. این تابع به برنامه‌ی شما بازنمی‌گردد و پس از فراخوانی‌اش برنامه‌ی‌تان پایان می‌یابد. مقدار status یکی از مقادیر INSIDE یا OUTSIDE استکه در فایل polygon.h تعریف شده‌اند.
برنامه‌ی شما نباید با هیچ فایل کار کرده، از ورودی بخواند یا به خروجی بنویسد. در ضمن برنامه‌ی شما نباید سعی کند که به فضایی خارج از برنامه دست‌رسی داشته باشد. بدیهی است که نقض هر یک از این حدود می‌تواند منجر به حذف شدن از گردونه‌ی رقابت‌ها گردد.
سه فایل polygon.h و polygonlib.cpp به شما داده شده است. بالای برنامه‌ی شما باید عبارت include polygon.h# را قرار دهید. توابع و تعاریفی که توسط کتاب‌خانه در اختیار شما قرار گرفته، به صورت زیر است:
#define INSIDE 0
#define OUTSIDE 1
struct point {
int x, y;
};
int init();
point get-query();
point get-vertex(int index);
void report(in status);
برای هم‌گردانی برنامه‌ی‌تان فایل‌های فوق‌الذکر را پیش برنامه‌ی‌تان کپی کرده و از دستور
g++ -02 –static polygon.cpp polygon.lib.cpp –lm
استفاده کنید. فایل spolygon.cpp نیز به شما داده شده، یک نمونه از کار کردن با این کتاب‌خانه است. توجه به دو نکته ضروری است:
- برنامه‌ی نمونه‌ی داده شده، یعنی
spolygon.cppکار مفیدی انجام نمی‌دهد و تنها برای نمایش نحوه‌ی کار کردن با کتاب‌خانه فراهم شده است. - در هنگام ارزیابی برنامه‌ها از کتاب‌خانه‌ی دیگری استفاده خواهد شد که توابع و تعاریف درون
polygon.hرا حمایت می‌کند.
ورودی
در سطر نخست ورودی باید $n$ را بنویسید. در سطر بعدی مختصات راس اصلی و $n$ سطر دیگر مختصات رئوس چندضلعی را نشان می‌دهد.
شما آزادید برنامه‌هایی که در اختیارتان قرار داده شده را تغییر دهید ولی توصیه می‌شود که فایل polygon.h را تغییر ندهید.
خروجی
محدودیت‌ها
- محدودیت زمان: ۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
