php教程 php手册 uva10012 不是你想象的那么简单的

uva10012 不是你想象的那么简单的

Jun 21, 2016 am 08:48 AM
center int lt put size

道题第一次做以为是一般的回溯题,最初的思路就是将各圆形全排列,放置新圆的时候让其与前一个圆相切,最后通过回溯得到矩形的最小size。十几分钟编完后结果WA,想了好一会发现问题所在,不能只让其与前一个圆相切(如果第一个圆很大,半径比方说是100,第二个圆很小,半径是1,第三个圆也很大,半径同样是100,放第三个圆的时候如果是和第二个圆相切则必定会与第一个圆相交,就不可以了)。然后就开始修改代码,然后就遇到了各种错误,断断续续地弄了一晚上加一上午。

首先想的是每次放一个圆形的时候还是先让其与前一个放置的圆相切,然后判断它与再之前放的圆是否相交,如不相交,则说明这样放是正确且最节省距离的,如果有任何一个圆与其相交,则说明不能与前一个圆相切,就再往前推一个,让其与前前个圆相切,再判断是否和别的圆相交。。。为了判断是否相交,增加了一个center数组存储各圆的圆心位置。到此思路很正确很清晰,然后遇到了三个Wa的点。

WA1:判断矩形最小size的时候不能用最后一个圆的最右侧位置了,因为有可能最后一个圆很小,其最右侧的位置还不如其前一个圆的最右侧位置远,所以改用判断各圆圆心位置+半径的最大值作为矩形的最小size。

WA2:在放置前几个圆的时候注意不能让圆的圆心位置-圆的半径<0。比如说第一个圆半径是1,第二个元半径100,放第二个元就不能让其与第一个圆相切因为那样圆的左边就超出矩形盒子的壁了!

WA3:主函数中MinL设置的太小,估计测试数据的数有很大的,题目没有说半径最大是多少,开始设的是65536,结果WA,改成DBL_MAX就AC了!!

#include#include#include#include#includeusing namespace std;  
  
int m,Put[10];          //Put[i]:放置的第i个圆的编号  
double MinL,size[10],center[10];//size[i]:编号为i的圆的半径;center[i]:放置的第i个圆的圆心位置  
bool vis[10];  
  
double getlen(int a,int b)      //计算两圆心间的距离  
{  
    return sqrt((size[a]+size[b])*(size[a]+size[b])-(size[a]-size[b])*(size[a]-size[b]));  
}  
bool isok(int a,int b)          //是否和之前放的圆相交  
{  
    for (int i=0;i<b;i++)  
    {  
        if (sqrt((center[i]-center[a])*(center[i]-center[a])+(size[Put[i]]-size[Put[a]])*(size[Put[i]]-size[Put[a]]))<(size[Put[i]]+size[Put[a]]))  
            return false;  
    }  
    return true;  
}  
void dfs(int cur)  
{  
    int i,j;  
    if (cur==m)  
    {     
        double maxsize=0;  
        for (int k=0;kmaxsize)  
                maxsize=center[k]+size[Put[k]];  
        }  
        if (maxsize<MinL)  
            MinL=maxsize;  
    }  
    else  
    {  
        for (i=0;i=0;j--)  
                {  
                    tmpl=getlen(Put[j],i);  
                    center[cur]=center[j]+tmpl;  
                    if (center[cur]-size[Put[cur]]>n;  
    while(n--)  
    {  
        cin>>m;  
        MinL=DBL_MAX;  
        memset(vis,0,sizeof(vis));  
        for (int i=0;i>size[i];  
        for (int i=0;i<m;i++)  
        {  
            Put[0]=i;  
            center[0]=size[i];  
            vis[i]=1;  
            dfs(1);  
            vis[i]=0;  
        }  
        cout<<fixed<<setprecision(3)<<MinL<<endl;  
    }  
    return 0;  
}
로그인 후 복사

【相关教程推荐】

1. php编程从入门到精通全套视频教程 

2. php从入门到精通  

3. bootstrap教程 

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

Acer Care Center 서비스가 아직 초기화 중입니다. [수정됨] Acer Care Center 서비스가 아직 초기화 중입니다. [수정됨] Mar 16, 2024 am 10:55 AM

이 문서에서는 Windows PC에서 Acer Care Center 서비스 초기화 오류 메시지 문제를 해결하는 방법을 안내합니다. AcerCareCenter 앱이 제대로 실행되지 않는 경우는 일반적으로 앱이 손상되었거나 오래되었거나 다른 소프트웨어와 충돌하기 때문입니다. Acer Care Center 서비스 초기화 중 오류 수정 Windows 11/10 PC에서 AcerCare Center 서비스 초기화 중 오류 메시지가 표시되는 경우 다음 제안 사항을 사용하여 문제를 해결하십시오. ACCStd.exe 프로세스를 다시 시작합니다. AcerCareCenter를 관리자로 실행 일시적으로 바이러스 백신을 비활성화합니다. 소프트웨어 클린 부팅 상태 확인 Acer Care 재설치 지원팀에 문의

Java의 File.length() 함수를 사용하여 파일 크기를 가져옵니다. Java의 File.length() 함수를 사용하여 파일 크기를 가져옵니다. Jul 24, 2023 am 08:36 AM

파일 크기를 얻으려면 Java의 File.length() 함수를 사용하십시오. 파일 크기는 파일 작업을 처리할 때 매우 일반적인 요구 사항입니다. Java는 파일 크기를 얻는 매우 편리한 방법, 즉 길이( ) File 클래스의 메서드입니다. 이 기사에서는 이 방법을 사용하여 파일 크기를 가져오는 방법을 소개하고 해당 코드 예제를 제공합니다. 먼저, 크기를 구하려는 파일을 나타내는 File 객체를 만들어야 합니다. File 객체를 생성하는 방법은 다음과 같습니다: Filef

PHP에서 int형을 바이트형으로 변환하는 방법에 대한 자세한 설명 PHP에서 int형을 바이트형으로 변환하는 방법에 대한 자세한 설명 Mar 06, 2024 pm 06:18 PM

PHP에서 int형을 byte로 변환하는 방법에 대한 자세한 설명 PHP에서는 네트워크 데이터 전송이나 파일 처리, 암호화 알고리즘 등을 다룰 때 정수형(int)을 byte(byte)형으로 변환해야 하는 경우가 많습니다. . 이번 글에서는 int형을 byte형으로 변환하는 방법을 자세히 소개하고 구체적인 코드 예시를 제공하겠습니다. 1. int형과 byte의 관계 컴퓨터 분야에서 기본 데이터형 int는 정수를 나타내고, byte(바이트)는 컴퓨터 저장 단위로 보통 8비트 바이너리 데이터이다.

double 유형 변수를 int 유형으로 변환하는 C++ 프로그램 double 유형 변수를 int 유형으로 변환하는 C++ 프로그램 Aug 25, 2023 pm 08:25 PM

C++에서 int 유형의 변수는 양수 또는 음수 정수 값만 보유할 수 있으며 소수 값은 보유할 수 없습니다. 이를 위해 float 및 double 값을 사용할 수 있습니다. double 데이터형은 소수점 이하 7자리까지 소수점 이하 자릿수를 저장하기 위해 만들어졌습니다. 정수를 double 데이터 형식으로 변환하는 것은 컴파일러에 의해 자동으로 수행되거나("암시적" 변환이라고 함) 프로그래머가 컴파일러에서 명시적으로 요청할 수 있습니다("명시적" 변환이라고 함). 다음 섹션에서는 다양한 변환 방법을 다룹니다. 암시적 변환 컴파일러는 암시적 유형 변환을 자동으로 수행합니다. 이를 달성하려면 부동 소수점 유형과 정수 유형의 두 가지 변수가 필요합니다. 단순히 부동 소수점 값이나 변수를 정수 변수에 할당하면 컴파일러가 다른 모든 사항을 처리합니다.

jQuery에서 PUT 요청 방법을 사용하는 방법은 무엇입니까? jQuery에서 PUT 요청 방법을 사용하는 방법은 무엇입니까? Feb 28, 2024 pm 03:12 PM

jQuery에서 PUT 요청 방법을 사용하는 방법은 무엇입니까? jQuery에서 PUT 요청을 보내는 방법은 다른 유형의 요청을 보내는 것과 유사하지만 몇 가지 세부 사항과 매개 변수 설정에 주의해야 합니다. PUT 요청은 일반적으로 데이터베이스의 데이터 업데이트 또는 서버의 파일 업데이트와 같은 리소스를 업데이트하는 데 사용됩니다. 다음은 jQuery에서 PUT 요청 메소드를 사용하는 구체적인 코드 예제입니다. 먼저 jQuery 라이브러리 파일을 포함했는지 확인한 다음 $.ajax({u를 통해 PUT 요청을 보낼 수 있습니다.

SpringBoot2의 PUT 요청이 매개변수를 수신할 수 없는 문제를 해결하는 방법 SpringBoot2의 PUT 요청이 매개변수를 수신할 수 없는 문제를 해결하는 방법 May 20, 2023 pm 08:38 PM

HiddenHttpMethodFilterhtml의 양식 양식은 GET 및 POST 요청만 지원하지만 DELETE 및 PUT와 같은 메소드는 지원되지 않습니다. Spring 3에서는 이러한 요청을 표준 http 메소드로 변환할 수 있는 필터를 추가하므로 GET, POST, PUT 및 DELETE 요청이 가능합니다. 지원됩니다. @BeanpublicFilterRegistrationBeantestFilterRegistration3(){FilterRegistrationBeanregistration=newFilterRegistrationBea

int32의 값 범위는 무엇입니까? int32의 값 범위는 무엇입니까? Aug 11, 2023 pm 02:53 PM

int32의 값 범위는 -2의 31승부터 2의 31승 - 1, 즉 -2147483648부터 2147483647까지입니다. int32는 부호 있는 정수 유형입니다. 즉, 양수, 음수 및 0을 나타낼 수 있습니다. 1비트를 사용하여 부호 비트를 나타내고 나머지 31비트는 숫자 값을 나타내는 데 사용됩니다. 부호비트를 표현하는데 1비트가 사용되므로 int32비트의 유효수는 31이다.

int는 몇 바이트를 차지합니까? int는 몇 바이트를 차지합니까? Jan 22, 2024 pm 03:14 PM

int 유형이 차지하는 바이트 수는 프로그래밍 언어 및 하드웨어 플랫폼에 따라 다를 수 있습니다. 자세한 소개: 1. C 언어에서 int 유형은 일반적으로 2바이트 또는 4바이트를 차지합니다. 32비트 시스템에서는 int 유형이 4바이트를 차지하고, 16비트 시스템에서는 int 유형이 2바이트를 차지합니다. 64비트 시스템에서 int 유형은 8바이트를 차지할 수 있습니다. 2. Java에서는 int 유형이 일반적으로 4바이트를 차지하는 반면, Python에서는 int 유형에 바이트 제한이 없으며 자동으로 조정될 수 있습니다.

See all articles