Пожалуйста, сообщите, какой случай я не освещаю - PullRequest
Новая
       41

Пожалуйста, сообщите, какой случай я не освещаю

0 голосов
/ 25 мая 2019
  • Учитывая 2 прямоугольника, параллельных координатным осям, найдите область, покрытую ими.

Формат ввода: Первая строка ввода содержитТ - количество тестовых случаев.Его сопровождают 2T строк.Первая строка каждого теста содержит 4 целых числа - xbl, ybl, xtr, ytr - нижняя левая и верхняя правая координаты прямоугольника-1.Вторая строка каждого теста содержит 4 целых числа - xbl, ybl, xtr, ytr - нижняя левая и верхняя правая координаты прямоугольника-2.

Ограничения

  • 1 <= T <= 10000 </li>
  • -10 6 6
  • (xbl, ybl) <(xtr, ytr) </li>

Формат вывода: Для каждого теста выведите область, покрытую двумя прямоугольниками, разделенные переводом строки.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

unsigned int recarea(int x1,int y1,int x2,int y2){
    int area=0;
    area=(x2-x1)*(y2-y1);
    return abs(area);
}

unsigned int overarea(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
    int top=fmin(y2,y4);
    int bottom=fmax(y1,y3);
    int left=fmax(x1,x3);
    int right=fmin(x2,x4);
    int overlaparea=0;
    if(bottom<top && left<right){
        overlaparea=recarea(left,bottom,right,top);
    }
    return abs(overlaparea);
}

int main() {
    int testcases=0;
    scanf("%d",&testcases);
    for(int i=0;i<testcases;i++){
        int x1,x2,y1,y2,x3,x4,y3,y4;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        scanf("%d %d %d %d",&x3,&y3,&x4,&y4);
        int area=recarea(x1,y1,x2,y2)+recarea(x3,y3,x4,y4)- 
         overarea(x1,y1,x2,y2,x3,y3,x4,y4);
        printf("%d\n",area);
    }   
    return 0;
}

Переменные x1, y1 - это нижние левые координаты, а x2, y2 - верхние правые координаты для Rectangle 1. Переменные x3, y3 - нижние левые координаты, а x4, y4 - верхние правые координаты для Rectangle 2.

1 Ответ

0 голосов
/ 26 мая 2019

Пожалуйста, сообщите, какой случай я не освещаю

Используйте более широкую математику

area=(x2-x1)*(y2-y1); склонен к переполнению int с учетом -10 6 6 .

Максимальная область составляет около 4 * 10 12 , вне диапазона большинства int реализаций (32 или 16 бит).

long long охватывает не менее диапазон - (2 63 + 1) ... + (2 63 + 1) 

long long recarea(int x1, int y1, int x2, int y2) {
    long long area = (0LL + x2 - x1)*(0LL + y2 - y1);
    return llabs(area);
}

   long long area = recarea(...
   printf("%lld\n",area);

Настроить overarea() тоже.

Другое

Могут существовать другие функциональные проблемы. Пример: int может быть размером до 16 бит. Попробуйте использовать long вместо этого для обработки -10 6 6 .

Помимо

Код использует функции с плавающей запятой с fmin(), fmax(). Я использовал бы только целочисленный подход, а не подвергался различным проблемам переключения между FP и целым числом. Здесь все в порядке, учитывая небольшой диапазон, но не для больших значений.

...