青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

我希望你是我獨(dú)家記憶

一段永遠(yuǎn)封存的記憶,隨風(fēng)而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首頁(yè) :: 新隨筆 ::  :: 聚合  :: 管理
//3348 Accepted 264K 0MS C++ 4016B 
//典型的凸包和計(jì)算多邊形面積

#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
#include 
<ctype.h>
#include 
<math.h>
#include 
<iostream>
using namespace std ;
#define unllong unsigned long long 
#define unint unsigned int
#define printline  printf( "\n" ) 
typedef 
long long llong ;
//const double PI = 2.0 * acos( 0.0 ) ;
#define zero(x) (((x)>0?(x):-(x))<eps)

const int Base=1000000000;//高精度
const int Capacity=100;//高精度
const double eps = 1e-8 ;
const int INF = 1000000 ;

const int size = 10010 ;

struct POINT
{
    
double x ;
    
double y ;
    
double k ;
};
struct POINT point[size] ;

int stack[size] ; 
int top = 2 ;

int inn ;
double outarea ;

double fdist( double x1, double y1, double x2, double y2 )
{
    
return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) ;
}

void input()
{
    
int leftdown = 0 ;
    
forint i=0; i<inn; i++ ) {
        scanf( 
"%lf %lf"&point[i].x, &point[i].y ) ;
        
//if( miny>point[i].y || miny==point[i].y&&minx>point[i].x )
        if( point[leftdown].y>point[i].y||zero(point[leftdown].y-point[i].y)&&point[leftdown].x>point[i].x )
            leftdown 
= i ;//找到最左下的點(diǎn)
    }
    
double temp ;
    temp 
= point[0].x ; point[0].x = point[leftdown].x ; point[leftdown].x = temp ;
    temp 
= point[0].y ; point[0].y = point[leftdown].y ; point[leftdown].y = temp ;
    
forint i=1; i<inn; i++ ) {
        point[i].k 
= atan2( point[i].y-point[0].y, point[i].x-point[0].x ) ;
    }
//以點(diǎn)(minx, miny)計(jì)算極角
}

double xmult( POINT &p1, POINT &p2, POINT &p0 )
{
//計(jì)算叉乘--線段旋轉(zhuǎn)方向和對(duì)應(yīng)的四邊形的面積--返回(p1-p0)*(p2-p0)叉積
    
//if叉積為正--p0p1在p0p2的順時(shí)針?lè)较? if(x==0)共線

    
return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y) ;
}

int gramcmp1( const void *a, const void *b )
{
    
struct POINT *= (struct POINT *)a ;
    
struct POINT *= (struct POINT *)b ;

    
if( c->- d->> eps )    return 1 ;
    
else if( c->- d->< -1*eps ) return -1 ;
    
else//斜率相等距離遠(yuǎn)的點(diǎn)在先
        return c->- d->> 0 ? 1 : -1 ;
}

int gramcmp( const void *a, const void *b )
{
    
struct POINT *= (struct POINT *)a ;
    
struct POINT *= (struct POINT *)b ;

    
double xmult_val = xmult( *c, *d, point[0] ) ;
    
if( xmult_val > eps )    return -1 ;
    
else if( xmult_val < -1*eps ) return 1 ;
    
else return c->- d->> 0 ? 1 : -1 ;
    
//else 
    
//return fdist( c->x,c->y,point[0].x,point[0].y )>fdist(d->x,d->y,point[0].x,point[0].y)? -1:1 ;
}

void gramham()
{
//凸包的點(diǎn)存在于stack[]中
    qsort( point+1, inn-1sizeof(point[1]), gramcmp ) ;//極坐標(biāo)排序--注意只有(n-1)個(gè)點(diǎn)

    
//int stack[size] ; int top = 2 ;
    stack[0= 0 ; stack[1= 1 ; stack[2= 2 ; top  = 2 ;

    
forint i=3; i<inn; i++ )
    {
        
while( top>=1&&xmult( point[i], point[stack[top]], point[stack[top-1]] )>=-1*eps ) 
            top
-- ;//順時(shí)針?lè)较?-刪除棧頂元素
        stack[++top] = i ;//新元素入棧
    }
    
/*
    for( int i=0; i<=top; i++ )
    {
    //printf( "%lf===%lf\n",point[stack[i]].x, point[stack[i]].y ) ;
    cout << point[stack[i]].x << "====" << point[stack[i]].y << endl ;
    }
    
*/
}

double flen_poly()
{
//計(jì)算凸包的周長(zhǎng)
    double len = 0.0 ; double x1, x2, y1, y2 ;
    
forint i=0; i<top; i++ ) {
        x1 
= point[stack[i+1]].x ; x2 = point[stack[i]].x ;
        y1 
= point[stack[i+1]].y ; y2 = point[stack[i]].y ;
        len 
+= fdist( x1, y1, x2, y2 ) ;
    }
    x1 
= point[stack[0]].x ; x2 = point[stack[top]].x ;
    y1 
= point[stack[0]].y ; y2 = point[stack[top]].y ;
    len 
+= fdist( x1, y1, x2, y2 ) ;

    
return len ;
}

double farea_poly( int n, POINT poly[] )
{
    
double area = 0.0 ; double s1 = 0.0 , s2 = 0.0 ;
    
forint i=0; i<n; i++ )
    {
        s1 
+= poly[stack[(i+1)%n]].y * poly[stack[i%n]].x ;
        s2 
+= poly[stack[(i+1)%n]].y * poly[stack[(i+2)%n]].x ;
    }

    
return fabs( s1 - s2 ) / 2 ;
}

void process()
{
    gramham() ;
//保存好凸包的點(diǎn)在stack[]中

    outarea 
= farea_poly( top+1, point ) ;
}

void output()
{
    printf( 
"%d\n", (int)outarea/50 ) ;
}

int main()
{
    
//freopen( "fc.in", "r", stdin ) ;
    
//freopen( "fc.out","w",stdout ) ;

    
//freopen( "in.txt", "r", stdin ) ;

    
while( scanf( "%d"&inn ) != EOF ) 
    {
        input() ;

        process() ;

        output() ;
    }

    
return 0 ;
}

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产一区欧美| 久久不射网站| 香蕉久久国产| 亚洲欧美精品suv| 欧美有码视频| 模特精品裸拍一区| 亚洲国产色一区| 亚洲黄色成人网| 99热这里只有精品8| 亚洲色诱最新| 欧美一区日韩一区| 免费欧美视频| 国产精品色午夜在线观看| 国产亚洲亚洲| 一本到12不卡视频在线dvd| 久久高清福利视频| 亚洲国产精品一区二区三区| 日韩视频一区二区三区在线播放| 一本色道久久综合精品竹菊| 欧美亚洲网站| 欧美精品一区二区三区很污很色的 | 欧美主播一区二区三区美女 久久精品人| 亚洲美女中出| 欧美综合77777色婷婷| 亚洲福利一区| 性xx色xx综合久久久xx| 欧美国产日韩a欧美在线观看| 欧美色欧美亚洲另类二区| 精品成人一区| 性伦欧美刺激片在线观看| 亚洲第一网站免费视频| 亚洲视频在线视频| 男人的天堂亚洲在线| 国产精品综合网站| 一区二区电影免费在线观看| 美女主播一区| 久久成人免费| 国产日韩欧美在线一区| 一区二区三区高清视频在线观看| 久久久国产精品一区| 国产精品99久久久久久久久久久久| 美女在线一区二区| 在线日韩欧美| 免费看的黄色欧美网站| 久久国产欧美精品| 国产永久精品大片wwwapp| 性欧美激情精品| 亚洲一区二区三区乱码aⅴ| 欧美激情一区二区三区蜜桃视频| 亚洲高清视频一区| 欧美成人中文字幕| 麻豆成人综合网| 精品成人在线视频| 鲁大师成人一区二区三区| 亚洲欧美日韩另类| 国产精品有限公司| 欧美中文字幕视频| 香蕉久久精品日日躁夜夜躁| 国产精品日本一区二区| 午夜一区在线| 欧美一级大片在线观看| 国产综合色产在线精品| 蜜桃久久av| 免费日韩成人| 亚洲精品一区二区在线| 欧美激情久久久久| 欧美高清一区| 亚洲综合色婷婷| 欧美一区国产在线| 亚洲国产另类久久精品| 亚洲精品国产品国语在线app| 欧美国产日本高清在线| 夜夜嗨一区二区| 在线亚洲+欧美+日本专区| 国产欧美一区二区三区久久| 久久影音先锋| 欧美激情免费观看| 亚洲女性裸体视频| 久久都是精品| 日韩一区二区久久| 亚洲影院一区| 伊人久久成人| 亚洲美女中文字幕| 欧美一区二区性| 91久久黄色| 在线视频欧美日韩| 精品91免费| 99国产精品视频免费观看| 国产女主播一区二区三区| 欧美国产激情| 国产精品视频网址| 亚洲高清在线视频| 国产精品日韩欧美一区二区| 理论片一区二区在线| 欧美三级韩国三级日本三斤| 久久天堂成人| 欧美婷婷久久| 欧美激情小视频| 国产伦精品一区二区三区视频孕妇| 美国十次了思思久久精品导航| 欧美日韩岛国| 免费亚洲一区| 国产日韩精品入口| 日韩午夜在线电影| 在线观看亚洲视频| 亚洲欧美成人一区二区三区| 亚洲精品视频免费在线观看| 亚洲欧美日韩精品久久| 一区二区三区视频在线观看| 免费观看不卡av| 美女被久久久| 国精品一区二区三区| 亚洲午夜精品视频| 亚洲美洲欧洲综合国产一区| 久久不射中文字幕| 欧美一区二区三区精品电影| 欧美日韩99| 亚洲韩国精品一区| 91久久久久久久久| 欧美/亚洲一区| 欧美黑人在线观看| 亚洲黄色在线看| 蜜臀久久99精品久久久久久9| 久久久久国产精品麻豆ai换脸| 国产精品对白刺激久久久| 亚洲日本在线视频观看| 91久久综合亚洲鲁鲁五月天| 久久久久久久一区| 久久综合久色欧美综合狠狠 | 欧美一级理论性理论a| 亚洲香蕉伊综合在人在线视看| 欧美成人综合在线| 欧美激情久久久久久| 亚洲激情亚洲| 欧美电影免费观看网站| 亚洲国产精品一区二区第一页| 亚洲精品偷拍| 欧美日韩一区二区三区在线| 正在播放欧美一区| 午夜精品免费视频| 国产欧美三级| 欧美一区三区三区高中清蜜桃 | 亚洲国产精品精华液网站| 在线成人av.com| 蜜桃av噜噜一区| 亚洲国产日韩一级| 一区二区三区产品免费精品久久75 | 欧美激情精品久久久六区热门| 伊人成人在线| 美国十次成人| 亚洲精品久久久一区二区三区| 一个色综合av| 国产精品系列在线播放| 午夜在线观看免费一区| 久久综合亚州| 国产精品99久久久久久久久久久久 | 欧美高清成人| 一区二区三区日韩欧美精品| 国产精品久久久久久av下载红粉| 香蕉成人久久| 欧美激情片在线观看| 中文亚洲视频在线| 狠狠色伊人亚洲综合成人| 欧美高清你懂得| 亚洲欧美日韩国产一区二区三区| 久久婷婷亚洲| 在线视频亚洲| 狠狠做深爱婷婷久久综合一区 | 一区二区日韩精品| 国产精品综合网站| 欧美成人激情在线| 亚洲欧美久久| 亚洲精品一区二区三区蜜桃久| 欧美在线一级va免费观看| 亚洲精品久久久久久下一站| 国产精品手机在线| 欧美激情一区二区三区在线视频| 亚洲免费在线观看| 亚洲精品网站在线播放gif| 久久性天堂网| 欧美一区二区精品| 亚洲午夜一区二区| 亚洲激情视频| 国语自产精品视频在线看8查询8| 欧美日韩视频不卡| 免费欧美日韩国产三级电影| 西西裸体人体做爰大胆久久久| 亚洲人成人一区二区三区| 久久精品视频一| 亚洲专区欧美专区| 一区二区av| 99日韩精品| 亚洲狠狠婷婷| 在线观看亚洲a| 好吊色欧美一区二区三区视频| 国产精品欧美精品| 欧美视频免费在线观看| 欧美精品1区| 欧美成人资源| 欧美成人综合|