f436 - 11498 - Division of Nlogonia
題目描述
題目描述了 Nlogonia 被劃分為四個國家，由一個分界點定義。給定分界點的座標 (N, M) 和一個待判斷點的座標 (X, Y)，需要判斷該點位於哪個國家。如果該點位於分界線上，則輸出 "divisa"。
解題思路
題目要求根據給定的點的座標，判斷其相對於分界點的位置。分界點定義了南北和東西兩個方向的線。
- 如果待判斷點的 x 座標等於分界點的 x 座標，或者 y 座標等於分界點的 y 座標，則該點位於分界線上，輸出 "divisa"。
- 否則，根據待判斷點的 x 座標和 y 座標與分界點的 x 座標和 y 座標的比較結果，判斷該點位於哪個象限，並輸出相應的國家名稱：
- 如果 x > N 且 y > M，則輸出 "NE"。
- 如果 x < N 且 y < M，則輸出 "SO"。
- 如果 x > N 且 y < M，則輸出 "SE"。
- 如果 x < N 且 y > M，則輸出 "NO"。
複雜度分析
- 時間複雜度: O(T * K)，其中 T 是測試案例的數量，K 是每個測試案例中查詢的數量。因為對於每個查詢，我們只需要進行常數次比較和輸出操作。
- 空間複雜度: O(1)，因為我們只需要存儲少量的整數變量。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline int read(){
int a(0),f(1);
char c('0');
while(c>='0'||c=='-'){
if(c=='-'){
f=-1;
c=getchar_unlocked();
}
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a*f;
}
int main(){
int t,n,m,a,b;
while(t=read()){
if(t==0)break;
n=read();
m=read();
while(t--){
a=read();
b=read();
if(a==n||b==m)
puts("divisa");
else if(a>n&&b>m){
putchar_unlocked('N');
putchar_unlocked('E');
putchar_unlocked('\n');
}
else if(a<n&&b<m){
putchar_unlocked('S');
putchar_unlocked('O');
putchar_unlocked('\n');
}
else if(a>n&&b<m){
putchar_unlocked('S');
putchar_unlocked('E');
putchar_unlocked('\n');
}
else{
putchar_unlocked('N');
putchar_unlocked('O');
putchar_unlocked('\n');
}
}
}
}