题目

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const double pi=acos(-1);
const int mod=100000000; struct Point{
double x,y;
//Point(){};
Point(double xx=0,double yy=0):x(xx),y(yy){}
bool read()
{
return ~scanf("%lf%lf", &x, &y);
}
bool operator<(const Point p) const{
if(this->x!=p.x)
return this->x<p.x;
else return this->y<p.y;
}
double dot(Point p)
{
return this->x*p.x+this->y*p.y;
}
double getA()
{
double A=atan2(this->y,this->x);
if(A<-pi/2+eps) A+=2*pi;
return A;
}
Point operator-(Point p)
{
return Point(this->x-p.x,this->y-p.y);
}
}; double det(Point p,Point q)
{
return p.x*q.y-q.x*p.y;
} int dcmp(double x)
{
if(fabs(x)<eps) return 0;
else if(x>0) return 1;
else return -1;
}
Point p[100005],ans[100005];
double ang[100005]; int Convex_hull(Point *p,int n,Point *ans)
{
sort(p+1,p+n+1);
ans[1]=p[1];ans[2]=p[2];
int w=2;
for(int i=3;i<=n;i++)
{
int k=dcmp(det(p[i]-ans[w-1],ans[w]-ans[w-1]));
while(dcmp(det(p[i]-ans[w-1],ans[w]-ans[w-1]))>0&&w>=2)
w--;
ans[++w]=p[i];
}
int cur=w;
ans[++w]=p[n-1];
for(int i=n-2;i>=2;i--)
{
int k=dcmp(det(p[i]-ans[w-1],ans[w]-ans[w-1]));
while(dcmp(det(p[i]-ans[w-1],ans[w]-ans[w-1]))>0&&w>=cur+1)
w--;
ans[++w]=p[i];
}
return w;
} int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++) p[i].read();
int m=0;
if(n>1) {m=Convex_hull(p,n,ans);}
ans[m+1]=ans[0];
for(int i=1;i<=m;i++)
ang[i]=(ans[i+1]-ans[i]).getA();
Point q[3];
while(q[1].read())
{
q[2].read();
int i=upper_bound(ang+1,ang+m+1,(q[2]-q[1]).getA())-ang;
int j=upper_bound(ang+1,ang+m+1,(q[1]-q[2]).getA())-ang;
if(n>1&&dcmp(det(q[2]-q[1],ans[i]-q[1]))*dcmp(det(q[2]-q[1],ans[j]-q[1]))<0)
printf("BAD\n");
else printf("GOOD\n");
}
}
return 0;
}

  

最新文章

  1. js判断地址转向
  2. Node.js与Sails~Model数据模型
  3. pitch yaw roll 的区别
  4. DotNetBar中ListViewEx控件的使用
  5. 自定义ViewPager控制是否滑动
  6. poj 2318 TOYS (二分+叉积)
  7. Installing Ubuntu on a Pre-Installed Windows 8 (64-bit) System (UEFI Supported)
  8. yii cgridview 对生成的数据进行分页
  9. RequireJS进阶(二)
  10. 链表-Partition List
  11. PHP+Apache怎样监控多个port和配置多网站
  12. 新概念英语(1-17)How do you do ?
  13. OAuth2.0学习(1-10)新浪开放平台微博认证-手机应用授权和refresh_token刷新access_token
  14. OpenStack-Neutron-Fwaas-代码【一】
  15. what are you 弄啥嘞!!!!!!!!!!!!!!!!泛型
  16. bzoj4842 Delight for a Cat
  17. Oracle Instance and Database
  18. Luogu4547 THUWC2017 随机二分图 概率、状压DP
  19. RBAC
  20. DTrace memory leak 内存泄露

热门文章

  1. djangourl进阶
  2. Spring MVC 中使用AOP 进行统一日志管理--XML配置实现
  3. oracle登录后无法使用,显示Connected to an idle instance
  4. 多个电脑上免密登陆命令、scp远程拷贝、修改文件的用户和组
  5. 第一课 初识Linux(一)
  6. mysql表优化
  7. 使用ActiveMQ实现JMS消息通信服务
  8. oracle 常用查询语句
  9. sql server 函数详解(1)字符串函数
  10. HBASE学习笔记(三)