poj-1066 Treasure Hunt
2187 단어 poj기타 문제 형OIer 문제 풀이 기록
100 크기 의 직사각형 방 이 있 고 방 안에 n 개의 벽 이 있다.
모든 벽 은 방 을 가로 지 르 고 세 개의 벽 이 하나 도 교차 하지 않 는 다.
방 안의 어떤 점 에 보물 이 있 는데 방 밖에서 몇 개의 벽 을 깨 면 보물 이 도착 할 수 있 는 곳 을 물 어보 자.
문제 풀이:
생각 이 매우 신기 한 문제;
먼저 비교적 직관 적 인 사 고 는 바로 대구 도 를 구축 하여 최 단 로 를 달 리 는 것 이다.
하지만 이 건 나 도 쓸 줄 모 르 잖 아.
이 벽 들 이 방 을 가로 지 르 는 특수성 을 감안 하면
신기 한 알고리즘 이 생 겼 어 요.
방 바깥쪽 의 점 을 매 거 하여 모든 벽의 출발점 과 종점 이 양쪽 에 있 는 지 판단 한다.
만약 양쪽 에 있다 면, 그림 속 에는 반드시 이 벽 을 지나 갈 것 이다!
사상 은 이렇다. 그 다음 에 시 뮬 레이 션 문제 다.
양쪽 위의 포크 의 곱 하기 < 0 을 판단 합 니 다.
코드:
#include
#include
#include
#include
#define N 33
using namespace std;
const double EPS=1e-8;
const double INF=1e100;
struct Point
{
double x,y;
Point(){}
Point(double _,double __):x(_),y(__){}
friend Point operator +(Point a,Point b)
{
return Point(a.x+b.x,a.y+b.y);
}
friend Point operator -(Point a,Point b)
{
return Point(a.x-b.x,a.y-b.y);
}
friend double operator *(Point a,Point b)
{
return a.x*b.x+a.y*b.y;
}
friend double operator ^(Point a,Point b)
{
return a.x*b.y-a.y*b.x;
}
}T;
int top[4];
double st[4][N];
struct Line
{
Point p,v;
void read()
{
static Point temp;
scanf("%lf%lf%lf%lf",&p.x,&p.y,&temp.x,&temp.y);
if(p.x==0)
st[0][++top[0]]=p.y;
if(p.x==100)
st[1][++top[1]]=p.y;
if(p.y==0)
st[2][++top[2]]=p.x;
if(p.y==100)
st[3][++top[3]]=p.x;
if(temp.x==0)
st[0][++top[0]]=temp.y;
if(temp.x==100)
st[1][++top[1]]=temp.y;
if(temp.y==0)
st[2][++top[2]]=temp.x;
if(temp.y==100)
st[3][++top[3]]=temp.x;
v=temp-p;
}
}l[N];
int main()
{
int n,m,i,j,k,x,y,ans,cnt;
double p;
scanf("%d",&n);
for(i=1;i<=n;i++)
l[i].read();
scanf("%lf%lf",&T.x,&T.y);
for(i=0,ans=0x3f3f3f3f;i<4;i++)
{
st[i][++top[i]]=100;
sort(st[i],st[i]+top[i]+1);
for(j=1;j<=top[i];j++)
{
if(fabs(st[i][j]-st[i][j-1]) 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
