d546: 3. 剪多邊形（molding）

/**********************************************************************************/
/*  Problem: d546 "3. 剪多邊形（molding）" from 北市 98 資訊學科能力競賽*/
/*  Language: CPP (1642 Bytes)                                                    */
/*  Result: AC(4ms, 442KB) judge by this@ZeroJudge                                */
/*  Author: monkey413 at 2012-08-02 14:51:55                                      */
/**********************************************************************************/


/*利用外積得知凸多邊形還是凹多邊形與凹點+多邊形面積公式*/
#include<iostream>
#include<cmath>
using namespace std;
int n,a,start,end;
float area=0 ;
int main()
{
    while(cin>>n>>a)
    {
        int coor[n][2],vec[n][2],cross[n]; /*坐標、向量、外積*/
        for(int i=0 ; i<n ; ++i) for(int j=0 ; j<2 ; ++j) cin >> coor[i][j] ;
        for(int i=0 ; i<n ; ++i)
        {
            if(i+1<n) vec[i][0]=coor[i+1][0]-coor[i][0],vec[i][1]=coor[i+1][1]-coor[i][1] ;
            else vec[i][0]=coor[0][0]-coor[i][0],vec[i][1]=coor[0][1]-coor[i][1] ;
        }
        for(int i=0 ; i<n ; ++i)
        {
            if(i+1<n) cross[i]=vec[i][0]*vec[i+1][1]-vec[i+1][0]*vec[i][1] ;
            else cross[i]=vec[i][0]*vec[0][1]-vec[0][0]*vec[i][1] ;
        }
        /*凹多邊形面積要補滿，才可以成為凹多邊形*/
        for(int i=0 ; i<n ; ++i)
        {
            if(cross[i]<0)
            {
                start=i ;
                end=i+2 ;
                for(int j=i+1 ; j<n ; ++j)
                {
                    if(cross[j]<0) end++ ;
                }
                for(int k=start ; k<=end ; ++k)
                {
                    /*cout << start << " "<< end << endl ;*/
                    if(k+1<n) area += (coor[k][0]*coor[k+1][1]-coor[k][1]*coor[k+1][0])/2 ;
                    else area += coor[k][0]*coor[k+1-n][1]-coor[k][1]*coor[k+1-n][0] ;
                }
                /*cout << area << endl;*/
            }
        }
        cout << ceil(area/a) << endl ;
        area=0 ;
    }
    return 0;
}