UESTC 1332 뷰 티 콘테스트 (볼록 직경)
2586 단어 test
제목: n 개의 점 을 정 하 다.최대한 멀리.
사고방식: 템 플 릿 문제.
View Code
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
struct point
{
double x,y;
point(){}
point(double _x,double _y)
{
x=_x;
y=_y;
}
void get()
{
scanf("%lf%lf",&x,&y);
}
};
const double EPS=1e-8;
const int MAX=100005;
point p[MAX],q[MAX];
int n,m;
int DB(double x)
{
if(x>EPS) return 1;
if(x<-EPS) return -1;
return 0;
}
double Dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
// p ab
// :
// :
// ab 0
double cross(point a,point b,point p)
{
return (b.x-a.x)*(p.y-a.y)-(b.y-a.y)*(p.x-a.x);
}
int cmp(point a,point b)
{
double x=Dis(a,p[0]),y=Dis(b,p[0]);
int flag=DB(cross(p[0],a,b));
if(flag) return flag==1;
return DB(x-y)<=0;
}
void Graham(point p[],int n,point q[],int &m)
{
point temp;
int i,k=0,a,b;
for(i=1;i<n;i++)
{
a=DB(p[i].y-p[k].y);
b=DB(p[i].x-p[k].x);
if(a==-1||!a&&b==-1) k=i;
}
if(k!=0) temp=p[0],p[0]=p[k],p[k]=temp;
sort(p+1,p+n,cmp);
q[0]=p[0];
q[1]=p[1];
p[n]=p[0];
m=2;
for(i=2;i<=n;i++)
{
while(m>1&&DB(cross(q[m-2],q[m-1],p[i]))<=0) m--;
q[m++]=p[i];
}
m--;
}
double calMaxLen(point q[],int n)
{
q[n]=q[0];
int i,p=1;
double ans=0,x,y;
for(i=0;i<n;i++)
{
while(1)
{
x=cross(q[i],q[i+1],q[p+1]);
y=cross(q[i],q[i+1],q[p]);
if(DB(x-y)<=0) break;
p=(p+1)%n;
}
ans=max(ans,max(Dis(q[i],q[p]),Dis(q[i+1],q[p+1])));
}
return ans;
}
int main()
{
while(scanf("%d",&n)!=-1)
{
int i;
for(i=0;i<n;i++) p[i].get();
Graham(p,n,q,m);
double ans=calMaxLen(q,m);
printf("%.0lf
",ans*ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Sorting Layer와 3D Object의 관계이것은 원래는 에 게재하고 있던 기사이지만, 뭐 자신의 블로그는 기술적인 기사를 도카도카 게재하는 장소도 아니기 때문에, 이쪽에도 병행해 게재해 둔다. 어느 날 질문을 받았다. "그러고 보니 unity에서 sorti...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.