用了trinkle的方法,半平面交转凸包。

写了一发,既没有精度误差,也很好写。

#include <map>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long struct Vector{
int x,y;
void print()
{
printf("Vector - > (%d,%d)\n",x,y);
}
}; struct Point{
int x,y;
int id;
void print()
{
printf("Point ID %d (%d,%d)\n",id,x,y);
}
}; Vector operator - (Point a,Point b)
{Vector ret;ret.x=a.x-b.x;ret.y=a.y-b.y;return ret;} ll operator * (Vector a,Vector b)
{return (ll)a.x*b.y-(ll)a.y*b.x;} int n,top=0;
Point a[50005],sta[50005]; bool cmp(Point a,Point b)
{return a.x==b.x?a.y<b.y:a.x<b.x;}
bool cmp2(Point a,Point b)
{return a.id<b.id;}
void Andrew()
{
F(i,1,n)
if (a[i].x!=a[i-1].x){
while (top>=2&&(sta[top]-sta[top-1])*(a[i]-sta[top])<=0) top--;
sta[++top]=a[i];
}
sort(sta+1,sta+top+1,cmp2);
F(i,1,top) printf("%d ",sta[i].id);
printf("\n");
} void Finout()
{
freopen("bzoj_1007.in","r",stdin);
freopen("bzoj_1007.out","w",stdout);
} int main()
{
// Finout();
scanf("%d",&n);
F(i,1,n)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].y=-a[i].y;
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
Andrew();
}

  

最新文章

  1. php实现设计模式之代理模式
  2. js 实现单行文本滚动效果
  3. push与concat
  4. 关于使用AIDL出现空指针的解决办法
  5. shell脚本积累
  6. eclipse下使用java调用weka(转)
  7. 【转载】HRTF音频3D定位技术综述
  8. pathload --有效的网络带宽估计方法
  9. HDU 4857 (反向拓扑排序 + 优先队列)
  10. C#写的客户端连接 php的服务器端的小例子
  11. HDU 4946 Area of Mushroom 凸包 第八次多校
  12. iOS基础 - KVC and KVO
  13. 《精通CSS》——个人总结
  14. python的历史与优劣
  15. A session had already been started – ignoring session_start() 怎么办?
  16. @Data注解使用后在eclipse中get/set报错解决方法
  17. python,列表,元祖,字典
  18. Python-Django&#160;第一个Django&#160;app
  19. [20190226]删除tab$记录的恢复6.txt
  20. Linux编程 3 (初识bash shell与man查看手册)

热门文章

  1. HDU 1964 Pipes (插头DP,变形)
  2. Chrome浏览器扩展程序的本地备份
  3. socket的BeginConnect(EndPoint remoteEP,AsyncCallback callback,objcet state);个人理解
  4. 实验3 分支&amp;循环语句(1)
  5. 模板类 vector
  6. Hibernate查询语句HQL8大特点
  7. Web服务器☞Apache VS Nginx
  8. 将Xcode的本地代码push到github仓库上
  9. sass --watch 失败bug
  10. [LUOGU] P2593 [ZJOI2006]超级麻将