poj 3348

裸的凸包,,我就来粘一下板子

把jls和dls的代码混合了一下(雾),感觉我要是能把camp里的几何掌握的差不多就稳         了。(mxy到底打了什么?)

感觉叉积实在是个好东西qwq

今晚cf还要不要打呢,,,可是这几天都是十一点多就早睡了。。。到时候神智不清怎么办,,,可是好想上个紫什么的。。。

 #include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef double db;
const db eps=1e-;
const db pi=acos(-);
int sign(db k){
if (k>eps) return ; else if (k<-eps) return -; return ;
}
int cmp(db k1,db k2){return sign(k1-k2);}
struct point{
db x,y;
point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
point operator / (db k1) const{return (point){x/k1,y/k1};}
bool operator == (const point &k1) const{return cmp(x,k1.x)==&&cmp(y,k1.y)==;}
bool operator <(const point &k1)const {
int c=cmp(x,k1.x);
if(c)return c==-;
return cmp(y,k1.y)==-;
}
};
db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}
int n;
vector<point> convexHull(vector<point> ps){
int n = ps.size();if(n<=)return ps;
sort(ps.begin(),ps.end());
vector<point> qs(n*);int k=;
for(int i=;i<n;qs[k++]=ps[i++])
while (k>&&cross(qs[k-]-qs[k-],ps[i]-qs[k-])<=)--k;
for(int i=n-,t=k;i>=;qs[k++]=ps[i--])
while (k>t&&cross(qs[k-]-qs[k-],ps[i]-qs[k-])<=)--k;
qs.resize(k-);
return qs;
}
vector<point>p;
db x,y;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%lf%lf",&x,&y);
p.push_back(point{x,y});
}
p=convexHull(p);
int m=p.size();
int ans=;
for(int i=;i<m;i++){
ans+=cross(p[i],p[(i+)%m]);
}
ans=abs(ans)/;
printf("%d\n",ans/);
}
上一篇:poj 3683(2-sat+输出一组可行解)


下一篇:ES6中的let和const