#include<cstdio>
#include<cmath>
#include<cstdlib>
#define eps 1e-5
#define sqr(x) ((x)*(x))
#define abs(x) ((x)>0?(x):0-(x))
using namespace std;
struct point{//{{{
    int x,y;
};//}}}
int n;
double area,len;
point p[10];
int cmp1(const void *a,const void *b){//{{{
    int x1=((point *)a)->x-p[0].x,x2=((point *)b)->x-p[0].x,y1=((point *)a)->y-p[0].y,y2=((point *)b)->y-p[0].y;
    int tmp=x1*y2-x2*y1;
    if(tmp!=0)return tmp;
    else return sqr(x1)+sqr(y1)-sqr(y2)-sqr(x2);
}//}}}
int cmp2(const void *a,const void *b){//{{{
    int tmp=((point *)a)->x-((point *)b)->x;
    if(tmp!=0)return tmp;
    else return ((point *)a)->y-((point *)b)->y;
}//}}}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&p[i].x,&p[i].y);
    qsort(p+1,n-1,sizeof(point),cmp1);
    for(int i=0;i<n-1;i++){
        area+=0.5*(p[i].y+p[i+1].y)*(p[i+1].x-p[i].x);
        len+=sqrt(sqr(p[i].x-p[i+1].x)+sqr(p[i].y-p[i+1].y));
    }
    area+=0.5*(p[n-1].y+p[0].y)*(p[0].x-p[n-1].x);
    len+=sqrt(sqr(p[n-1].x-p[0].x)+sqr(p[n-1].y-p[0].y));
    if(abs(area)<eps){
        qsort(p,n,sizeof(point),cmp2);
        len=sqrt(sqr(p[0].x-p[n-1].x)+sqr(p[0].y-p[n-1].y));
    }
    printf("%.2lf\n%.2lf",len,abs(area));
    return 0;
}

向量外积+逆时针算一圈+共线特判，AC无压力

一直wa一个点啊，怎么特判啊，求大神
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN=10000+1;
struct Point
{
double x,y;
}p[MAXN],s[MAXN];
int n,top;
double ans,area;
double dist(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double slope(Point a,Point b)
{
return (a.y-b.y)/(a.x-b.x);
}
double h(Point a,Point b,Point c)
{
if(b.x==c.x) return abs(b.x-a.x);
else if(b.y==c.y) return abs(a.y-b.y);
else
{
double k=slope(b,c);
return abs(k*a.x-a.y-k*c.x+c.y)/sqrt(k*k+1.0);
}
}
double mul(Point a,Point b,Point c)
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
bool cmp(const Point &a,const Point &b)
{
if(mul(a,b,p[0])>0) return 1;
if(mul(a,b,p[0])==0&&dist(a,p[0])<dist(b,p[0])) return 1;
return 0;
}
void graham()
{
top=2;
int i,k=0;
bool flag=false;
for(i=1;i<n;i++)
if((p[k].y>p[i].y)||p[k].y==p[i].y&&p[k].x>p[i].x) k=i;
swap(p[0],p[k]);
sort(p+1,p+n,cmp);
s[0]=p[0],s[1]=p[1],s[2]=p[2];
for(i=3;i<n;i++)
{
while(top&&mul(p[i],s[top],s[top-1])>=0) top--;
s[++top]=p[i];
}
s[++top]=p[0];
for(i=0;i<top;i++)
ans+=dist(s[i],s[i+1]);
for(i=1;i<top;i++)
area+=dist(s[i],s[i+1])*h(p[0],s[i],s[i+1])/2;
for(i=1;i<top;i++)
if(s[i].y!=s[i+1].y)
{
flag=true;
break;
}
if(flag==false) area=0;
}
int main(int argc, char *argv[])
{
int i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
graham();
printf("%.2f\n",ans);
printf("%.2f\n",area);
return 0;
}

凸包+叉积？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

排序只用叉积会错1~2个点，因为与基准点共线的点没考虑。

叉积排序后我又把和基准点共线的点确认排序方向然后排了个序就对了。。

最后一个点求数据。。

第七个点和最后一个点出问题应该是所有点共线处理时出的问题。

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

恩...

第七个数据是什么

怎么算的出0.00来........

天哪....

这题快让我疯了...

最后一个点死都过不去...

有没有数据

program jyh;

var

q1,q2,q3,s,l:real;

n,i:integer;

x,y:array [1..100] of real;

function sjx(a,b,c:real):real;

var

p:real;

begin

p:=(a+b+c)/2;

sjx:= sqrt( p*(p-a)*(p-b)*(p-c) );

end;

begin

readln(n);

for i:=1 to n do

readln(x[i],y[i]);

s:=0;

for i:=2 to n-1 do

begin

q1:=sqrt( (x[i]-x[1])*(x[i]-x[1])+(y[i]-y[1])*(y[i]-y[1]) );

q2:=sqrt( (x-x[i])*(x-x[i])+(y-y[i])*(y-y[i]) );

q3:=sqrt( (x-x[1])*(x-x[1])+(y-y[1])*(y-y[1]) );

s:=s+sjx(q1,q2,q3);

end;

for i:=1 to n-1 do

begin

q2:=sqrt( (x-x[i])*(x-x[i])+(y-y[i])*(y-y[i]) );

l:=l+q2;

end;

writeln(l:0:2);

writeln(s:0:2);

end.

最弱的方法，全排列

原来想把凸包程序直接打一遍交上去，结果挂了一个点。

自己分析是特判一下直线情况

ac……

第150个通过，纪念下…………

此题卡了我n天，最后得出一个结论：

此题必须写凸包!!

抓狂ing，偷懒只写极角排序死也过不去

将N个点按顺时针排序(极角排序),然后求周长和面积就是几句话

for i:=1 to n-1 do

c:=c+sqrt(sqr(b.x-b[i].x)+sqr(b.y-b[i].y));

c:=c+sqrt(sqr(b[1].x-b[n].x)+sqr(b[1].y-b[n].y));

for i:=2 to n-1 do

s:=s+hl(b[1],b[i],b);

if s=0 then c:=c/2;

注意如果所有的点不是一条直线,那么它们必然构成凸包,并且所有的点都在凸包上,切记切记,注意注意

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 181ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：181ms

DFS!!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 10：答案错误...　├ 标准行输出

　├ 错误行输出

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：40 有效耗时：0ms

why????????

var

r,t:integer;

p,i,j,n,ww:integer;

min1,min2,w,d,tots,totc,x,y:real;

kk1:array[1..10]of real;

kk2:array[1..10]of integer;

cost:array[1..10,1..2]of real;

procedure try(x1,y1,x2,y2:real);

var

a,b,c,p:real;

begin

a:=sqrt(sqr(x-x1)+sqr(y-y1));

b:=sqrt(sqr(x-x2)+sqr(y-y2));

c:=sqrt(sqr(x1-x2)+sqr(y1-y2));

p:=(a+b+c)/2;

tots:=tots+sqrt(p*(p-a)*(p-b)*(p-c));

totc:=totc+c;

end;

begin

readln(n);

readln(cost[1,1],cost[1,2]);

for i:=2 to n do

begin

readln(cost,cost);kk2[i]:=i;

if cost-cost[1,1] 0 then

kk1[i]:=(cost-cost[1,2])/(cost-cost[1,1])

else kk1[i]:=32767;

end;

if nmin1 then begin

min1:=min2;

end

else begin

kk2[i]:=kk2[t];

end

end;

t:=i;

until kk1[t]kk1[n];

totc:=totc+min1;

x:=cost[1,1];y:=cost[1,2];

tots:=0;

for i:=r-1 to t do

if kk1[i]kk1 then

try(cost[kk2[i],1],cost[kk2[i],2],cost[kk2,1],cost[kk2,2])

;

writeln(totc:0:2);

writeln(tots:0:2);

end.

??????????????????????????

?????????????????????????

......原来求面积是分成三角形再用海伦公式。我还以为用Monte-Carlo算法。都是被这个难度给蒙的。

应该没有比我时间长的了吧:

├ 测试数据 08：答案正确... 384ms

我想了个偷懒的办法,根本不用凸包

用next_permutation()...

第一个点定下来,全排列阿

在周长最小的时候,那么它就是凸包了吧?

注意一下周长除2的事情要放到最后做,不然样例都过不了.