poj 3968 (bzoj 2642)
二分+半平面交，每次不用排序，这是几个算几版综合。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
using namespace std;
#define MAXN 100000
namespace geometry
{
typedef long double real;
const real pi=3.1415926535897;
const real eps=1e-;
inline real sqr(real x)
{
return x*x;
}
inline int sgn(real x)
{
if (abs(x)<eps)return ;
return x<?-:;
}
class point
{
public:
real x,y;
point(){x=y=;}
point(real x,real y):x(x),y(y){};
void read();
void print();
};
inline void point::read()
{
double xx,yy;
scanf("%lf%lf\n",&xx,&yy);
x=xx;y=yy;
}
inline void point::print()
{
printf("Point:[%.2lf,%.2lf]\n",(double)x,(double)y);
}
inline real dis(point p1,point p2)
{
return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
}
inline bool cmp_point_position(point p1,point p2)
{
if (p1.y!=p2.y)return p1.y<p2.y;
return p1.x<p2.x;
}
class line
{
public:
point ps;
point pt;
line(){}
line(point ps,point pt):ps(ps),pt(pt){}
line(point ps,real dx,real dy);
real len();
real angle();
bool leftside(point pp);
bool rightside(point pp);
void print();
point mid_point();
line mid_vertical();
};
inline real dot(line& l1,line& l2)
{
return (l1.pt.x-l1.ps.x)*(l2.pt.x-l2.ps.x)
+(l1.pt.y-l1.ps.y)*(l2.pt.y-l2.ps.y);
}
inline real det(line l1,line l2)
{
return (l1.pt.x-l1.ps.x)*(l2.pt.y-l2.ps.y) -
(l1.pt.y-l1.ps.y)*(l2.pt.x-l2.ps.x);
} line::line(point ps,real dx,real dy)
{
this->ps=ps;
this->pt.x=ps.x+dx;
this->pt.y=ps.y+dy;
}
inline real line::len()
{
return sqrt(sqr(pt.x-ps.x)+sqr(pt.y-ps.y));
}
inline real line::angle()
{
return atan2(pt.x-ps.x,pt.y-ps.y);
//if (pt.y>=ps.y)
// return -(pt.x-ps.x)/len();
//else
// return (pt.x-ps.x)/len()+10; //if (pt.y>=ps.y)
// return acos((pt.x-ps.x)/len());
//else
// return 2*pi-acos((pt.x-ps.x)/len()); }
inline bool line::leftside(point pp)
{
return sgn(det(line(pp,ps),*this))>;
}
inline bool line::rightside(point pp)
{
return sgn(det(line(pp,ps),*this))<;
}
inline void line::print()
{
printf("Line:[%.2lf,%.2lf] -> [%.2lf,%.2lf]\n",(double)ps.x,(double)ps.y,(double)pt.x,(double)pt.y);
} point line::mid_point()
{
return point((ps.x+pt.x)/,(ps.y+pt.y)/);
}
line line::mid_vertical()
{
return line(mid_point(),pt.y-ps.y,ps.x-pt.x);
}
inline real operator *(line l1,line l2)
{
return det(l1,l2);
}
inline line operator -(point p1,point p2)
{
return line(p2,p1);
}
inline bool parallel(line l1,line l2)
{
//return sgn(l1.angle()-l2.angle())==0;
return sgn(det(l1,l2))==;
}
inline point crossover(line l1,line l2)
{
if (!sgn(det(l1,l2)))throw ;
real s1=det(l1,l2.ps-l1.ps);
real s2=-det(l1,l2.pt-l1.ps);
return point(l2.ps.x+s1/(s1+s2)*(l2.pt.x-l2.ps.x),
l2.ps.y+s1/(s1+s2)*(l2.pt.y-l2.ps.y));
}
inline real area(point p1,point p2,point p3)
{
return det(line(p2,p1),line(p3,p1))/;
}
typedef line halfplane;
inline bool cmp_line_angle(line l1,line l2)
{
return sgn(l2.angle()-l1.angle())<;
}
inline bool cmp_halfplane(halfplane p1,halfplane p2)
{
int res=sgn(p1.angle()-p2.angle());
if (!res)return !p2.rightside(p1.ps);
return res<;
}
halfplane hpi_que[MAXN];
point hpi_pt_que[MAXN];
void halfplane_intersection(vector<halfplane> &vec,vector<point> &res)
{
sort(vec.begin(),vec.end(),cmp_halfplane);
res.clear();
hpi_que[]=vec[];
int head=,tail=;
point pt;
for (register int i=;i<(int)vec.size();i++)
{
if (parallel(vec[i],vec[i-]))continue;
while (head<tail && vec[i].rightside(hpi_pt_que[tail-]))
tail--;
while (head<tail && vec[i].rightside(hpi_pt_que[head]))
head++;
hpi_que[++tail]=vec[i];
if (!sgn(det(hpi_que[tail],hpi_que[tail-])) && hpi_que[tail].rightside(hpi_que[tail-].ps))
{
res.clear();return ;
}
hpi_pt_que[tail-]=crossover(hpi_que[tail],hpi_que[tail-]);
}
while (head<tail && hpi_que[head].rightside(hpi_pt_que[tail-]))
tail--;
while (head<tail && hpi_que[tail].rightside(hpi_pt_que[head]))
head++;
if (head==tail)
return;
for (register int i=head;i<tail;i++)
res.push_back(hpi_pt_que[i]);
if (tail->head)
res.push_back(crossover(hpi_que[head],hpi_que[tail]));
return ;
}
real area(vector<point> &vec)
{
register real ans=;
for (register int i=;i<(int)vec.size();i++)
{
ans+=area(point(,),vec[i],vec[(i+)%vec.size()]);
}
return abs(ans);
}
void convex_hull(vector<point> &vec,vector<point> &res)
{
res.clear();
res.push_back(vec[]);
for (int i=;i<(int)vec.size();i++)
{
while (res.size()> && !(line(res[res.size()-],res[res.size()-])).leftside(vec[i]))
res.pop_back();
res.push_back(vec[i]);
}
int h=(int)vec.size();
for (int i=(int)vec.size()-;i>=;i++)
{
while ((int)res.size()>h && !(line(res[res.size()-],res[res.size()-])).leftside(vec[i]))
res.pop_back();
res.push_back(vec[i]);
}
res.pop_back();
}
class circle
{
public:
point ct;
real r;
circle(){ct=point(,),r=;};
circle(point ct,real r):ct(ct),r(r){};
circle(point p1,point p2,point p3)
{
line l1=line(p1,p2).mid_vertical();
line l2=line(p1,p3).mid_vertical();
ct=crossover(l1,l2);
r=dis(ct,p1);
}
bool inside(point pt);
bool on_border(point pt);
bool outside(point pt);
};
bool circle::inside(point pt)
{
return sgn(r-dis(pt,ct))>;
}
bool circle::on_border(point pt)
{
return sgn(r-dis(pt,ct))==;
}
bool circle::outside(point pt)
{
return sgn(r-dis(pt,ct))<;
}
}
using namespace geometry; int topv=-;
vector<halfplane> vv;
vector<point> ans;
point pl[MAXN];
int main()
{
freopen("input.txt","r",stdin);
int i;
int n;
scanf("%d",&n);
for (i=;i<n;i++)
pl[i].read();
int l=,r=n/,mid;
while (l+<r)
{
mid=(l+r)>>;
vv.clear();
for (i=;i<n;i++)
vv.push_back(line(pl[(i+mid+)%n],pl[i]));
halfplane_intersection(vv,ans);
if (sgn(area(ans)>))
{
l=mid;
}else
{
r=mid;
}
}
printf("%d\n",r);
}
bzoj1336
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
using namespace std;
#define MAXN 510000
namespace geometry
{
typedef long double real;
const real pi=3.14159265358979323846264338;
const real eps=1e-;
inline real sqr(real x)
{
return x*x;
}
inline int sgn(real x)
{
if (abs(x)<eps)return ;
return x<?-:;
}
class point
{
public:
real x,y;
point()
{
x=y=;
}
point(real x,real y):x(x),y(y){};
void read()
{
double xx,yy;
scanf("%lf%lf\n",&xx,&yy);
x=xx;y=yy;
}
void print()
{
printf("Point:[%.2lf,%.2lf]\n",(double)x,(double)y);
}
};
real dis(point p1,point p2)
{
return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
}
bool cmp_point_position(point p1,point p2)
{
if (p1.y!=p2.y)return p1.y<p2.y;
return p1.x<p2.x;
}
point mid_point(point p1,point p2)
{
return point((p1.x+p2.x)/,(p1.y+p2.y)/);
}
class line
{
public:
point ps;
point pt;
line(){}
line(point ps,point pt):ps(ps),pt(pt){}
line(point ps,real dx,real dy);
real len();
real angle();
bool leftside(point pp);
void print();
point mid_point();
line mid_vertical();
};
real dot(line l1,line l2)
{
return (l1.pt.x-l1.ps.x)*(l2.pt.x-l2.ps.x)
+(l1.pt.y-l1.ps.y)*(l2.pt.y-l2.ps.y);
}
real det(line l1,line l2)
{
return (l1.pt.x-l1.ps.x)*(l2.pt.y-l2.ps.y) -
(l1.pt.y-l1.ps.y)*(l2.pt.x-l2.ps.x);
}
line::line(point ps,real dx,real dy)
{
this->ps=ps;
this->pt.x=ps.x+dx;
this->pt.y=ps.y+dy;
}
real line::len()
{
return sqrt(sqr(pt.x-ps.x)+sqr(pt.y-ps.y));
}
real line::angle()
{
return atan2(pt.x-ps.x,pt.y-ps.y);
/*
if (pt.y>=ps.y)
return -(pt.x-ps.x)/len();
else
return (pt.x-ps.x)/len()+1e5;*/
/*
if (pt.y>=ps.y)
return acos((pt.x-ps.x)/len());
else
return 2*pi-acos((pt.x-ps.x)/len());
*/
}
bool line::leftside(point pp)
{
return sgn(det(line(pp,ps),*this))>;
}
void line::print()
{
printf("Line:[%.2lf,%.2lf] -> [%.2lf,%.2lf]\n",(double)ps.x,(double)ps.y,(double)pt.x,(double)pt.y);
}
point line::mid_point()
{
return point((ps.x+pt.x)/,(ps.y+pt.y)/);
}
line line::mid_vertical()
{
return line(mid_point(),pt.y-ps.y,ps.x-pt.x);
}
real operator *(line l1,line l2)
{
return det(l1,l2);
}
line operator -(point p1,point p2)
{
return line(p2,p1);
}
bool parallel(line l1,line l2)
{
return sgn(det(l1,l2))==;
}
point crossover(line l1,line l2)
{
real s1=det(l1,l2.ps-l1.ps);
real s2=-det(l1,l2.pt-l1.ps);
return point(l2.ps.x+s1/(s1+s2)*(l2.pt.x-l2.ps.x),
l2.ps.y+s1/(s1+s2)*(l2.pt.y-l2.ps.y));
}
real area(point p1,point p2,point p3)
{
return (p2-p1)*(p3-p1)/;
}
typedef line halfplane;
bool cmp_line_angle(line l1,line l2)
{
return sgn(l2.angle()-l1.angle())<;
}
bool cmp_halfplane(halfplane p1,halfplane p2)
{
int res=sgn(p1.angle()-p2.angle());
if (!res)return p2.leftside(p1.ps);
return sgn(res)<;
}
void halfplane_intersection(vector<halfplane> vec,vector<point> &res)
{
sort(vec.begin(),vec.end(),cmp_halfplane); /*for (int i=0;i<(int)vec.size();i++)
{
vec[i].print();
printf("%.5lf\n",(double)vec[i].angle());
}*/
deque<halfplane> q;
deque<point> ans;
q.clear(),ans.clear();
// vec[0].print();
// printf("%.5lf\n",(double)vec[0].angle());
point pt;
q.push_back(vec[]);
for (int i=;i<(int)vec.size();i++)
{
// vec[i].print();
// printf("%.5lf\n",(double)vec[i].angle());
if (parallel(vec[i],vec[i-]))continue;
while (ans.size() && !vec[i].leftside(ans.back()))
{
ans.pop_back();
q.pop_back();
}
while (ans.size() && !vec[i].leftside(ans.front()))
{
ans.pop_front();
q.pop_front();
}
if (parallel(vec[i],q.back()))
{
res.clear();
return ;
}
pt=crossover(vec[i],q.back());
ans.push_back(pt);
q.push_back(vec[i]);
}
bool flag=true;
while (flag)
{
flag=false;
while (ans.size() && !q.front().leftside(ans.back()))
ans.pop_back(),q.pop_back(),flag=true;
while (ans.size() && !q.back().leftside(ans.front()))
ans.pop_front(),q.pop_front(),flag=true;
}
if (q.size()>=)
{
pt=crossover(q.back(),q.front());
ans.push_back(pt);
}
res=vector<point>(ans.begin(),ans.end());
return ;
}
real area(vector<point> &vec)
{
real ans=;
for (int i=;i<(int)vec.size();i++)
{
ans+=area(point(,),vec[i],vec[(i+)%vec.size()]);
}
return abs(ans);
}
void convex_hull(vector<point> vec,vector<point> &res)
{
sort(vec.begin(),vec.end(),cmp_point_position);
res.clear();
res.push_back(vec[]);
for (int i=;i<vec.size();i++)
{
while (res.size()> && !(line(res[res.size()-],res[res.size()-])).leftside(vec[i]))
res.pop_back();
res.push_back(vec[i]);
}
int h=vec.size();
for (int i=vec.size()-;i>=;i++)
{
while (res.size()>h && !(line(res[res.size()-],res[res.size()-])).leftside(vec[i]))
res.pop_back();
res.push_back(vec[i]);
}
res.pop_back();
}
class circle
{
public:
point ct;
real r;
circle(){ct=point(,),r=;};
circle(point ct,real r):ct(ct),r(r){};
circle(point p1,point p2,point p3)
{
line l1=line(p1,p2).mid_vertical();
line l2=line(p1,p3).mid_vertical();
ct=crossover(l1,l2);
r=dis(ct,p1);
}
bool inside(point pt);
bool on_border(point pt);
bool outside(point pt);
};
bool circle::inside(point pt)
{
return sgn(r-dis(pt,ct))>;
}
bool circle::on_border(point pt)
{
return sgn(r-dis(pt,ct))==;
}
bool circle::outside(point pt)
{
return sgn(r-dis(pt,ct))<;
}
}; using namespace geometry;
int topv=-;
point pl[MAXN];
int main()
{
freopen("input.txt","r",stdin);
int i,j,k;
int n;
scanf("%d",&n);
for (i=;i<n;i++)
pl[i].read();
for (i=;i<n*;i++)
swap(pl[rand()%n],pl[rand()%n]);
circle cnow;
for (i=;i<n;i++)
{
if (cnow.outside(pl[i]))
{
cnow=circle(pl[i],);
for (j=;j<i;j++)
{
if (cnow.outside(pl[j]))
{
cnow.ct=mid_point(pl[i],pl[j]);
cnow.r=dis(pl[i],pl[j])/;
for (k=;k<j;k++)
{
if (cnow.outside(pl[k]))
{
cnow=circle(pl[i],pl[j],pl[k]);
}
}
}
}
}
}
printf("%.10lf\n",(double)cnow.r);
printf("%.10lf %.10lf\n",(double)cnow.ct.x,(double)cnow.ct.y);
}
poj 2451
必须交c++，如果用g++会wa，我在提交界面刷了六页的屏。。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
using namespace std;
#define MAXN 51000
namespace geometry
{
typedef long double real;
const real pi=3.1415926535897;
const real eps=1e-;
inline real sqr(real x)
{
return x*x;
}
inline int sgn(real x)
{
if (abs(x)<eps)return ;
return x<?-:;
}
class point
{
public:
real x,y;
point(){x=y=;}
point(real x,real y):x(x),y(y){};
void read();
void print();
};
inline void point::read()
{
double xx,yy;
scanf("%lf%lf\n",&xx,&yy);
x=xx;y=yy;
}
inline void point::print()
{
printf("Point:[%.2lf,%.2lf]\n",(double)x,(double)y);
}
inline real dis(point p1,point p2)
{
return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
}
inline bool cmp_point_position(point p1,point p2)
{
if (p1.y!=p2.y)return p1.y<p2.y;
return p1.x<p2.x;
}
class line
{
public:
point ps;
point pt;
line(point ps,point pt):ps(ps),pt(pt){}
line(){}
real len();
real angle();
bool leftside(point pp);
bool rightside(point pp);
void print(); };
inline real dot(line& l1,line& l2)
{
return (l1.pt.x-l1.ps.x)*(l2.pt.x-l2.ps.x)
+(l1.pt.y-l1.ps.y)*(l2.pt.y-l2.ps.y);
}
inline real det(line l1,line l2)
{
return (l1.pt.x-l1.ps.x)*(l2.pt.y-l2.ps.y) -
(l1.pt.y-l1.ps.y)*(l2.pt.x-l2.ps.x);
}
inline real line::len()
{
return sqrt(sqr(pt.x-ps.x)+sqr(pt.y-ps.y));
}
inline real line::angle()
{
//return atan2(pt.x-ps.x,pt.y-ps.y);
/* if (pt.y>=ps.y)
return -(pt.x-ps.x)/len();
else
return (pt.x-ps.x)/len()+10;*/ if (pt.y>=ps.y)
return acos((pt.x-ps.x)/len());
else
return *pi-acos((pt.x-ps.x)/len()); }
inline bool line::leftside(point pp)
{
return sgn(det(line(pp,ps),*this))>;
}
inline bool line::rightside(point pp)
{
return sgn(det(line(pp,ps),*this))<;
}
inline void line::print()
{
printf("Line:[%.2lf,%.2lf] -> [%.2lf,%.2lf]\n",(double)ps.x,(double)ps.y,(double)pt.x,(double)pt.y);
}
inline real operator *(line l1,line l2)
{
return det(l1,l2);
}
inline line operator -(point p1,point p2)
{
return line(p2,p1);
}
inline bool parallel(line l1,line l2)
{
return sgn(l1.angle()-l2.angle())==;
//return sgn(det(l1,l2))==0;
}
inline point crossover(line l1,line l2)
{
if (!sgn(det(l1,l2)))throw ;
real s1=det(l1,l2.ps-l1.ps);
real s2=-det(l1,l2.pt-l1.ps);
return point(l2.ps.x+s1/(s1+s2)*(l2.pt.x-l2.ps.x),
l2.ps.y+s1/(s1+s2)*(l2.pt.y-l2.ps.y));
}
inline real area(point p1,point p2,point p3)
{
return det(line(p2,p1),line(p3,p1))/;
}
typedef line halfplane;
inline bool cmp_line_angle(line l1,line l2)
{
return sgn(l2.angle()-l1.angle())<;
}
inline bool cmp_halfplane(halfplane p1,halfplane p2)
{
int res=sgn(p1.angle()-p2.angle());
if (!res)return !p2.rightside(p1.ps);
return res<;
}
halfplane q[MAXN];
point qp[MAXN];
void halfplane_intersection(vector<halfplane> &vec,vector<point> &res)
{
sort(vec.begin(),vec.end(),cmp_halfplane);
int x=;
//for (int i=0;i<(int)vec.size();i++)
// {
// vec[i].print();
//printf("%.5lf\n",(double)vec[i].angle());
// }
// vec[0].print();
// printf("%.5lf\n",(double)vec[0].angle());
res.clear();
q[]=vec[];
int head=,tail=;
point pt;
//vec[0].print();
for (register int i=;i<(int)vec.size();i++)
{
//vec[i].print();
if (parallel(vec[i],vec[i-]))continue;
while (head<tail && vec[i].rightside(qp[tail-]))
tail--;
while (head<tail && vec[i].rightside(qp[head]))
head++;
q[++tail]=vec[i];
if (!sgn(det(q[tail],q[tail-])) && q[tail].rightside(q[tail-].ps))
{
res.clear();return ;
}
qp[tail-]=crossover(q[tail],q[tail-]);
}
while (head<tail && q[head].rightside(qp[tail-]))
tail--;
while (head<tail && q[tail].rightside(qp[head]))
head++;
if (head==tail)
{
return;
}
for (register int i=head;i<tail;i++)
res.push_back(qp[i]);
if (tail->head)//???
res.push_back(crossover(q[head],q[tail]));
return ;
}
real area(vector<point> &vec)
{
register real ans=;
for (register int i=;i<(int)vec.size();i++)
{
ans+=area(point(,),vec[i],vec[(i+)%vec.size()]);
}
return abs(ans);
}
void convex_hull(vector<point> &vec,vector<point> &res)
{
res.clear();
res.push_back(vec[]);
for (int i=;i<(int)vec.size();i++)
{
while (res.size()> && !(line(res[res.size()-],res[res.size()-])).leftside(vec[i]))
res.pop_back();
res.push_back(vec[i]);
}
int h=vec.size();
for (int i=(int)vec.size()-;i>=;i++)
{
while (res.size()>h && !(line(res[res.size()-],res[res.size()-])).leftside(vec[i]))
res.pop_back();
res.push_back(vec[i]);
}
res.pop_back();
}
}
using namespace geometry;
int topv=-;
vector<halfplane> vv;
vector<point> ans;
point pl[MAXN];
int main()
{
//freopen("input.txt","r",stdin);
int i;
int n;
while (~scanf("%d",&n) && ~n)
{
point pt;
vv.clear();
vv.push_back(line(point(,),point(,)));
vv.push_back(line(point(,),point(,)));
vv.push_back(line(point(,),point(,)));
vv.push_back(line(point(,),point(,)));
double a,b,c,d;
for (i=;i<n;i++)
{
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
vv.push_back(line(point(a,b),point(c,d)));
}
// crossover(vv[4],vv[5],pt);
halfplane_intersection(vv,ans);
// for (i=0;i<(int)ans.size();i++)
// ans[i].print();
printf("%.1lf\n",(double)area(ans));
}
}