====== چند ضلعی ======
یکی از دوستان به تازگی یاد گرفته که برنامههای هندسهی محاسباتی بنویسد: مساحت شکل رو حساب میکند و تشخیص میدهد که آیا نقطهای درون یک چند ضلعی محدب هست یا خیر و از این دست.
عمو شایان به این دوست ما میگوید: «اگر راست میگی، برای چندضلعیهای غیر محدب این کار رو بکن!» این دوست ما هم عوض سرخورده شدن، ادعا میکند که میتواند با زمان کمتر از خطی مسئله را حل کند. فقط یک مشکل کوچک وجود دارد: ورودی مسئله $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'' را تغییر ندهید.
===== خروجی =====
===== محدودیتها =====
* محدودیت زمان: ۵ ثانیه
* محدودیت حافظه: ۲۵۶ مگابایت
===== ورودی و خروجی نمونه =====
^ ورودی نمونه ^ خروجی نمونه ^
| | |
* [[سوال ۱۱|سوال بعد]]
* [[سوال ۹|سوال قبل]]