- it
- 凸包 极角排序
const int maxn
=1005;
const double eps
=1e-10;
struct point
{
int x
;
int y
;
point(){}
point(int xx
,int yy
):x(xx
),y(yy
){}
bool friend operator <(const point
&a
,const point
&b
){
if(a
.x
==b
.x
) return a
.y
<b
.y
;
return a
.x
<b
.x
;
}
bool friend operator ==(const point
&a
,const point
&b
){
return a
.x
==b
.x
&&a
.y
==b
.y
;
}
bool friend operator !=(const point
&a
,const point
&b
){
return !(a
==b
);
}
point
friend operator -(const point
&a
,const point
&b
){
return point(a
.x
-b
.x
,a
.y
-b
.y
);
}
}p
[maxn
],O
,q
[2*maxn
+10];
bool cmp(point a
,point b
)
{
return a
.x
*b
.y
>a
.y
*b
.x
;
}
double cross2(point a
,point b
,point c
)
{
return (c
.x
-a
.x
)*(b
.y
-a
.y
)-(c
.y
-a
.y
)*(b
.x
-a
.x
);
}
bool cmp1(point p2
,point p3
)
{
return cross2(O
,p2
,p3
)<eps
;
}
double cross(point a
,point b
){
return a
.x
*b
.y
-b
.x
*a
.y
;
}
double dis(point a
,point b
){
return sqrt((a
.x
-b
.x
)*(a
.x
-b
.x
)+(a
.y
-b
.y
)*(a
.y
-b
.y
));
}
int PointOffLine( point pt
, point start
, point end
)
{
return ((pt
.x
- end
.x
)*(start
.y
- end
.y
)-(start
.x
- end
.x
)*(pt
.y
- end
.y
));
}
int n
,m
;
double Andrew(){
sort(p
,p
+n
);
m
=0;
for(int i
=0;i
<n
;i
++){
while(m
>1&&cross(q
[m
-1]-q
[m
-2],p
[i
]-q
[m
-2])<=0) m
--;
q
[m
++]=p
[i
];
}
int o
=m
;
for(int i
=n
-2;i
>=0;i
--){
while(m
>o
&&cross(q
[m
-1]-q
[m
-2],p
[i
]-q
[m
-2])<=0) m
--;
q
[m
++]=p
[i
];
}
if(n
>1) m
--;
double ans
=0;
for(int i
=1;i
<m
;i
++){
ans
+=dis(q
[i
],q
[i
-1]);
}
return ans
+dis(q
[0],q
[m
-1]);
}
double Melkman(){
int head
,tail
;
head
=tail
=n
;
q
[tail
++]=p
[0];
int i
;
for(i
=0;i
<n
-1;i
++){
q
[tail
]=p
[i
];
if(cross(p
[i
]-q
[head
],p
[i
+1]-q
[head
])) break;
}
if(n
==1) return 0;
if(n
==2) return dis(p
[0],p
[1]);
if(n
==3){
return dis(p
[0],p
[1])+dis(p
[0],p
[2])+dis(p
[1],p
[2]);
}
q
[--head
]=q
[++tail
]=p
[++i
];
if(cross(q
[n
+1]-q
[n
],q
[n
+2]-q
[n
])<0) swap(q
[n
],q
[n
+1]);
for(++i
;i
<n
;i
++){
if(cross(q
[tail
]-q
[tail
-1],p
[i
]-q
[tail
-1])>0
&&cross(q
[head
]-q
[head
+1],p
[i
]-q
[head
+1])<0) continue;
while(tail
-head
>1&&cross(q
[tail
]-q
[tail
-1],p
[i
]-q
[tail
-1])<=0) tail
--;
q
[++tail
]=p
[i
];
while(tail
-head
>1&&cross(q
[head
]-q
[head
+1],p
[i
]-q
[head
+1])>=0) head
++;
q
[--head
]=p
[i
];
}
double ans
=0;
for(int i
=head
;i
<tail
;i
++){
ans
+=dis(q
[i
],q
[i
+1]);
}
return ans
;
}
double Area()
{
if(m
<3)return 0;
int i
;
double ret
=0.0;
for(i
=2; i
<m
; i
++)
{
ret
+=fabs(cross2(q
[0],q
[i
-1],q
[i
])/2.0);
}
return ret
;
}
double RC(int len
){
int t
=1;
double ans
=dis(p
[0],p
[1]);
for(int i
=0;i
<len
;i
++){
while(abs(cross(p
[(i
+1)%len
]-p
[i
],p
[t
]-p
[i
]))
<abs(cross(p
[(i
+1)%len
]-p
[i
],p
[(t
+1)%len
]-p
[i
])))
t
=(t
+1)%len
;
ans
=max(ans
,max(dis(p
[t
],p
[i
]),dis(p
[(i
+1)%len
],p
[t
])));
}
return ans
;
}
