- it
- 半平面交
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std
;
#define eps 1e-8
const int MAXN
=10017;
int n
;
double r
;
int cCnt
,curCnt
;
struct point
{
double x
,y
;
};
point points
[MAXN
],p
[MAXN
],q
[MAXN
];
void getline(point x
,point y
,double &a
,double &b
,double &c
)
{
a
= y
.y
- x
.y
;
b
= x
.x
- y
.x
;
c
= y
.x
* x
.y
- x
.x
* y
.y
;
}
void initial()
{
for(int i
= 1; i
<= n
; i
++)p
[i
] = points
[i
];
p
[n
+1] = p
[1];
p
[0] = p
[n
];
cCnt
= n
;
}
point
intersect(point x
,point y
,double a
,double b
,double c
)
{
double u
= fabs(a
* x
.x
+ b
* x
.y
+ c
);
double v
= fabs(a
* y
.x
+ b
* y
.y
+ c
);
point pt
;
pt
.x
=(x
.x
* v
+ y
.x
* u
) / (u
+ v
);
pt
.y
=(x
.y
* v
+ y
.y
* u
) / (u
+ v
);
return pt
;
}
void cut(double a
,double b
,double c
)
{
curCnt
= 0;
int i
;
for(i
= 1; i
<= cCnt
; ++i
)
{
if(a
*p
[i
].x
+ b
*p
[i
].y
+ c
>= 0)q
[++curCnt
] = p
[i
];
else
{
if(a
*p
[i
-1].x
+ b
*p
[i
-1].y
+ c
> 0)
{
q
[++curCnt
] = intersect(p
[i
],p
[i
-1],a
,b
,c
);
}
if(a
*p
[i
+1].x
+ b
*p
[i
+1].y
+ c
> 0)
{
q
[++curCnt
] = intersect(p
[i
],p
[i
+1],a
,b
,c
);
}
}
}
for(i
= 1; i
<= curCnt
; ++i
)p
[i
] = q
[i
];
p
[curCnt
+1] = q
[1];
p
[0] = p
[curCnt
];
cCnt
= curCnt
;
}
void solve()
{
initial();
for(int i
= 1; i
<= n
; ++i
)
{
double a
,b
,c
;
getline(points
[i
],points
[i
+1],a
,b
,c
);
cut(a
,b
,c
);
}
}
int main()
{
int t
;
scanf("%d",&t
);
while(t
--)
{
scanf("%d",&n
);
for(int i
= 1; i
<= n
; i
++)
{
scanf("%lf%lf",&points
[i
].x
,&points
[i
].y
);
}
points
[n
+1] = points
[1];
solve();
if(cCnt
< 1)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
