Expert스터디 2일차(2016.05.26)

선분교차

• 선분의 끝점이 만나면 어떻게 처리해야 하는가?

  1. box_checking(A,B,C,D)
  2. ccw_checking(A,B,C,D)=
  ccw(A,B,C)*ccw(A,B,D)<0
  &&  ccw(C,D,A)*ccw(C,D,B)<0

볼록껍질

• 여러분은 angle 대신 ccw를 이용하여야 한다.
• 볼록껍질 상의 모든 점들을 포함시켜야 하는가?

  
  int comp(Point p1, Point p2)
  {
  if(ccw(O,p1,p2)!=0)
      return p1.angle < p2.angle;
  if(p1.angle == min_angle)
      return p1.dist < p2.dist;
  return p1.dist>p2.dist;
  }

O = point with minimum y

int stack[10000]; int top=0;

stack[++top] = 1; for(int i=2;i<=n;++i) { while(top>=2 && ccw(끝2개, a[i])<0) --top; stack[++top]=i; }

지난시간에 이어 CCW심화학습.

Convexhull을통해 좌표들의 최대거리를 구해봤고, 최소거리구하는 문제도 접해봄

두 선분이 교차하는지 판별하는방법으로 CCW+Box_Checking을 하면 된다는 걸 배움

문제번호

1. 1725

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define LL long long

__inline LL MAX(LL a, LL b) {

return a > b ? a : b;

}

int main() {

LL stack[100001];

LL N, stack_start;

scanf("%lld", &N);

LL arr[100001];

for (int i = 0; i < N; i++)

{

scanf("%lld", &arr[i]);

}

arr[N] = 0;

stack_start = -1;

LL Answer = 0;

for (int i = 0; i <= N; i++)

{

while (stack_start != -1 && arr[stack[stack_start]] >= arr[i])

{

LL height = arr[stack[stack_start]];

LL width;

stack_start--;

if (stack_start == -1)

{

width = i;

}

else {

width = i - stack[stack_start] - 1;

}

Answer = MAX(Answer, height * width);

}

stack_start++;

stack[stack_start] = i;

}

printf("%lld\n", Answer);

}

2. 11003

3. 11758

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int x1, y1, x2, y2;

int CCW(int x3, int y3) {

int tmp = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3);

if (tmp == 0) return 0;

return tmp > 0 ? 1 : -1;

}

int main() {

int x3, y3;

scanf("%d %d", &x1, &y1);

scanf("%d %d", &x2, &y2);

scanf("%d %d", &x3, &y3);

printf("%d", CCW(x3, y3));

}

4. 2166

5. 6439

6. 1708

7. 10254

8. 2261