다각형 이 돌출 다각형 인지 오목 다각형 인지 판단 하 다.
3746 단어 알고리즘
다각형 이 돌출 다각형 인지 오목 다각형 인지 판단 하 다.
입력:
여러 그룹의 테스트 데 이 터 를 포함 하 는 데 이 터 를 입력 하 십시오. 각 그룹의 데 이 터 는 2 줄 을 차지 합 니 다. 먼저 한 줄 은 정수 n 이 고 다각형 정점 의 개 수 를 표시 합 니 다. 그 다음 한 줄 은 2 입 니 다.×n 개의 정수, 시계 반대 순 서 를 나타 내 는 n 개의 정점 좌표 (xi, yi), n 이 0 일 때 입력 을 끝 냅 니 다.
출력:
모든 테스트 인 스 턴 스 에 대해 서 는 땅 덩이 의 모양 이 돌출 다각형 이 라면 'convex' 를 출력 하 십시오. 그렇지 않 으 면 출력 'concave' 를 출력 하 십시오. 모든 인 스 턴 스 의 출력 은 한 줄 을 차지 합 니 다.
해석:
벡터 의 수량 적 (내 적, 점 적) 벡터 의 벡터 적 (외 적, 포크 적) 은 오른손 규칙 에 부합된다.
벡터 적 은 위 벡터 로 그 방향 을 수직 으로 포크 적 을 하 는 두 개의 벡터 로 정의 하고 오른손 규칙 을 만족시킨다.
벡터 포크 의 기하학 적 의미
1. 벡터 의 포크 적 모 는 이 두 벡터 가 둘 러 싼 평행 사각형 의 면적 을 나타 낸다.
벡터 P = (x1, y1), Q = (x2, y2),
벡터 포크 적 정 의 를 이유 로 (0, 0), p1, p2 와 p1 + p2 로 구 성 된 평행 사각형 의 기호 면적, 즉
P×Q = x1*y2 – x2*y1 그 결 과 는 가짜 벡터 이다.분명히 성질 이 있다 P× Q = – ( Q × P) 와 P× ( – Q ) = – ( P × Q )。
2. 포크 의 매우 중요 한 특징 은 그의 기 호 를 통 해 두 벡터 간 의 시계 반대 관 계 를 판단 할 수 있다 는 것 이다.
4. 벡터 포크 는 이 두 벡터 평면 의 법 적 벡터 이기 때문에 만약 에 두 벡터 가 평행 으로 하나의 평면 을 형성 하지 못 하면 그 대응 도 평면 법 벡터 가 없다. 그래서 두 벡터 가 평행 할 때 그 벡터 포크 는 0 이다.
코드:
#include
#include
struct xy
{
int x;
int y;
}d[1000];
int g(int a,int b,int c)
{
int t;
// :s=(x1-x3)*(y2-y3)-(x2-x3)*(y1-y3)
// s>0 ,p1,p2,p3
// s<0 ,p1,p2,p3
t=(d[a].x-d[c].x)*(d[b].y-d[c].y)-(d[b].x-d[c].x)*(d[a].y-d[c].y);
return t;
}
int main()
{
int i,t,n;
while(scanf("%d",&n),n)
{
for(i=0;iscanf("%d %d",&d[i].x,&d[i].y);
}
for(i=0;i// n i=n-1 n+1,n+2 ,
t=g(i%n,(i+1)%n,(i+2)%n);
if(t<0)
break;
}
if(t>=0)
printf("convex
");
else
printf("concave
");
}
return 0;
} 이 글 은 다음 에서 전 재 됩 니 다:https://www.cnblogs.com/wushuaiyi/archive/2013/12/05/3458659.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
