---
title: 'Compute Area of Rectangle'
tags: Coding Practice
---
# Compute Area of Rectangle
contributed by < `ChongMingWei` >

## Outline
[TOC]

## 題目
給定一含有4個座標點的字串，坐標皆位於 Cartesian grid 上(皆為整數坐標點)，給定的順序不為一定，請計算出該矩形的面積。
E.g.
- input
`{"(-1 2)","(4 -1)", "(4 2)", "(-1 -1)"}`
- output
`15`

## 實作流程
- 首先需要將給定的字串中，所有的座標資料分析出來，使用到 `strtok` 來切出數字的部分，接著使用 `strtol` 來將切出的數字字串轉變為 `long` 的資料型太後，映射到 `int` 資料型態儲存。
這邊我們只需要選擇前三組座標即可，原因如下:
- 我們使用三組座標，會形成一個直角三角形，而我們可以藉由此三組座標得到三個不同的向量，其中必定會有兩個向量互相垂直，只要得到這兩個向量，就可以用外積來計算矩形面積。

> 參考 [外積公式](https://read01.com/zh-tw/EQjg88.html#.X39XLMIzaM9)
- 計算面積: 使用外積的方式，但此處我們只有二維，但仍可已將其擴充到三維坐標:
$v1 = (x1,y1),\ v2=(x2,y2)>>v1 = (x1,y1,0),\ v2=(x2,y2,0)$
此時我們只需要計算 $x1y1-x2y2$ ，最後將此外積結果加上絕對值 $|x1y1-x2y2|$ 就是我們要求的面積。

## 程式碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
typedef struct vector{
    int x;
    int y;
}vec;
//使用外積來計算矩形面積
int compute_cross(vec v1, vec v2){
    int area = (v1.x*v2.y-v2.x*v1.y);
    //取絕對值
    int mask = area>>31;
    return (area + mask) ^ mask;
}
int compute_area(char **a, int len){
    int *coords = malloc(sizeof(int)*(len-1)*2);
    const char *lp = "(";
    const char *rp = ")";
    const char *s = " ";
    /*This kind is also ok
     * char lp[] = "(";
    char rp[] = ")";
    char s[] = " ";*/
    for (int i =0;i<len-1;i++){
        char *first=NULL, *second=NULL;//分別用來放空格前、後的字串
        char *buf;
        buf = malloc(sizeof(char)*(strlen(a[i])+1));//strlen得到的會是去到`\0`的長度，所以+1
        strncpy(buf, a[i], strlen(a[i])+1);
        first = strtok(buf, s);
        second = strtok(NULL, s);
        //以'('來切割，這邊'('前沒有字串，會返回'('後的字串，也就是x坐標
        char *num1 = strtok(first, lp);
        //string轉long，再映射成int
        coords[2*i] = strtol(num1,NULL,10);
        //以')'來切割，返回')'前的字串，也就是y坐標
        char *num2 = strtok(second, rp);
        //string轉long，再映射成int
        coords[2*i+1] = strtol(num2,NULL,10);
        //釋放記憶體
        free(buf);

    }
    //前三組座標形成的三個向量
    vec v1, v2, v3;
    v1.x = coords[2]-coords[0];
    v1.y = coords[3]-coords[1];
    v2.x = coords[4]-coords[0];
    v2.y = coords[5]-coords[1];
    v3.x = coords[4]-coords[2];
    v3.y = coords[5]-coords[3];
    //分別計算內積，若為0表示夾角為90度，使用外積計算面積並返回
    if ((v1.x*v2.x+v1.y*v2.y)==0)
        return compute_cross(v1,v2);
    else if((v1.x*v3.x+v1.y*v3.y)==0)
        return compute_cross(v1,v3);
    else 
        return compute_cross(v2,v3);
    //釋放記憶體
    free(coords);


}

int main(int argc, char *argv){
    char *a[] = {"(-1 2)","(4 -1)", "(4 2)", "(-1 -1)"};
    int len = sizeof(a) / sizeof(*a);
    int area = compute_area(a,len);
    printf("result:%d\n",area);
    return 0;
}

### strtok的使用
當我們在使用 `strtok` 時，欲分割的字串必須要"可修改"，因為欲分割的字串本身會遭到 `strtok` 修改，如以下範例:

int main(int argc, char *argv){
    char s[] = " ";
    char test[] = "(4 -1)";
    char *buf = malloc(sizeof(test));
    strcpy(buf,test);
    printf("%s\n",buf);
    char *first = strtok(buf, s);
    printf("%s\n",buf);
    char *first2 = strtok(NULL, s);
    printf("%s\n",buf);
    printf("%s\n",first);
    printf("%s\n",first2);
    return 0;
}

輸出結果:

(4 -1) //原本的 buf
(4     //經過strtok處理過後的buf
(4     
(4     //first
-1)    //first2

如果改成以下:

int main(int argc, char *argv){
    char s[] = " ";
    char *buf = "(4 -1)";//內容不可被修改
    printf("%s\n",buf);
    char *first = strtok(buf, s);
    printf("%s\n",buf);
    char *first2 = strtok(NULL, s);
    printf("%s\n",buf);
    printf("%s\n",first);
    printf("%s\n",first2);
    return 0;
}

輸出結果:

執行期間發生錯誤（RE） #stdin #stdout 0s 4176KB