裸的凸包。。。(和旋转卡壳有什么关系吗。。。蒟蒻求教T T)

话说忘了怎么写了。。。(我以前都是先做上凸壳再做下凸壳的说)

于是看了下hzwer的写法,用了向量的点积,方便多了,于是果断学习(Orz)了!

竟然比原作者要快T T

 /**************************************************************
Problem: 1670
User: rausen
Language: C++
Result: Accepted
Time:16 ms
Memory:900 kb
****************************************************************/ #include <cstdio>
#include <cmath>
#include <algorithm> #define points P
using namespace std;
typedef long long ll;
const int N = ;
int n, top;
double ans;
struct points{
int x, y;
}p[N], s[N]; inline ll operator * (const P a, const P b){
return a.x * b.y - a.y * b.x;
} inline P operator - (const P a, const P b){
P tmp;
tmp.x = a.x - b.x, tmp.y = a.y - b.y;
return tmp;
} inline ll Sqr(const ll x){
return x * x;
} inline ll dis(const P a, const P b){
return Sqr(a.x - b.x) + Sqr(a.y - b.y);
} inline bool operator < (const P a, const P b){
ll tmp = (a - p[]) * (b - p[]);
return tmp == ? dis(p[], a) < dis(p[], b) : tmp > ;
} inline int read(){
int x = , sgn = ;
char ch = getchar();
while (ch < '' || ch > ''){
if (ch == '-') sgn = -;
ch = getchar();
}
while (ch >= '' && ch <= ''){
x = x * + ch - '';
ch = getchar();
}
return sgn * x;
} int work(){
int k = ;
for (int i = ; i <= n; ++i)
if (p[i].y < p[k].y || (p[i].y == p[k].y && p[i].x < p[k].x)) k = i;
swap(p[], p[k]);
sort(p + , p + n + );
top = , s[] = p[], s[] = p[];
for (int i = ; i <= n; ++i){
while ((s[top] - s[top - ]) * (p[i] - s[top]) <= ) --top;
s[++top] = p[i];
}
s[top + ] = p[];
for (int i = ; i <= top; ++i)
ans += sqrt(dis(s[i], s[i + ]));
} int main(){
n = read();
for (int i = ; i <= n; ++i)
p[i].x = read(), p[i].y = read();
work();
printf("%.2lf\n", ans);
}
04-26 00:04