题目链接
Wannafly挑战赛21A
题解
代码
#include <cstdio>
#include <cmath>
#define MAX 1000005
#define Pi 3.14159265
struct Point{
double x,y;
void input() {
scanf("%lf%lf",&x,&y);
}
void output() {
printf("%f %f\n", x,y);
}
}p[MAX],s[MAX];
Point XZ(Point* p) {
return (Point){sin(Pi/4.0)*p->x+sin(Pi/4.0)*p->y, sin(Pi/4.0)*p->x-sin(Pi/4.0)*p->y};
}
bool cmp1(Point* a, Point* b) {return a->x<b->x;}
bool cmp2(Point* a, Point* b) {return a->y>b->y;}
bool cmp3(Point* a, Point* b) {return a->y<b->y;}
bool cmp4(Point* a, Point* b) {return a->x>b->x;}
int main () {
int T, n;
scanf ("%d", &T);
while (T--){
scanf("%d",&n);
for (int i = 0; i < n; i += 1)
p[i].input();
for (int i = 0; i < n; i += 1)
s[i] = XZ(p+i);
Point *a,*b,*c,*d;
a=b=c=d=&p[0];
for (int i = 1; i < n; i += 1){
if (cmp1(p+i,a))a=p+i;
if (cmp2(p+i,b))b=p+i;
if (cmp3(p+i,c))c=p+i;
if (cmp4(p+i,d))d=p+i;
}
if (a==b||a==c||d==b||d==c){
printf("Yes\n");
continue;
}
a=b=c=d=&s[0];
for (int i = 1; i < n; i += 1){
if (cmp1(s+i,a))a=s+i;
if (cmp2(s+i,b))b=s+i;
if (cmp3(s+i,c))c=s+i;
if (cmp4(s+i,d))d=s+i;
}
if (a==b||a==c||d==b||d==c){
printf("Yes\n");
continue;
}
printf("No\n");
}
return 0;
}