---
title: Codeforce 613 A. Peter and Snow Blower 解析(思維、幾何)
description: "Codeforce 613 A. Peter and Snow Blower 解析(思維、幾何)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 613 A. Peter and Snow Blower 解析(思維、幾何)">
<!-- toc -->

# Codeforce 613 A. Peter and Snow Blower 解析(思維、幾何)
今天我們來看看CF613A
[題目連結](https://codeforces.com/problemset/problem/613/A)

> **題目**
給你一個點$P$和$n$個點形成的多邊形(照順或逆時針順序給)，求這個多邊形繞著$P$轉最後可以造成的面積。(有關正式的"旋轉"定義請看原題)

### 前言
儲存點的座標時沒想過要用$pair<long\ long,long\ long>$，結果debug超久

### 想法
首先要注意到:由於題目的旋轉的定義是把每個點都對於點$P$去做旋轉，所以最後的圖形一定是兩個同心圓，而面積就是兩個圓中間的面積，而我們只需要維護最長的半徑和最短的半徑就好。
由於題目是按照順序給多邊形的點，所以我們可以把每條邊單獨拿出來考慮和$P$點的最短和最長距離。
如上圖所示，想要判斷點$P$到線段$\overline{SE}$的最短距離線段是否在線段$\overline{SE}$上，我們只需要判斷$\overrightarrow{PM}$是否被$\overrightarrow{PS},\overrightarrow{PE}$所包住，而其中一種方法就是利用外積(叉積、cross product):
如果$\overrightarrow{PM}$是被包住的，那麼$sgn(\overrightarrow{PM}\times\overrightarrow{PS})=-sgn(\overrightarrow{PM}\times\overrightarrow{PE})$
反之如果$sgn(\overrightarrow{PM}\times\overrightarrow{PS})=sgn(\overrightarrow{PM}\times\overrightarrow{PE})$，那麼代表沒有被包住。以上是利用了外積的性質:$\overrightarrow{AB}\times\overrightarrow{CD}=-\overrightarrow{CD}\times\overrightarrow{AB}$對於任何向量$\overrightarrow{AB},\overrightarrow{CD}$。
而要計算最短距離，我們有兩種方法:
1. 利用內積是投影長度的相乘的性質，我們把線段的法向量和$\overrightarrow{PE}$作內積，再除以法向量的長度，就是最短距離。
2. 利用外積的絕對值是向量們所展出的四邊形面積，且等於底乘以高，$|\overrightarrow{PS}\times\overrightarrow{PE}|/|\overrightarrow{SE}|$就是最短距離。

而透過觀察可以發現，$P$點到線段的長度，不是最短距離，那就是端點。有了以上資訊，我們就可以寫了。

### 程式碼:

const int _n=1e5+10;
int t,n,m;
PII p,prev,ps[_n];
db minn=1e9,maxx=-1e9,pi=acos(-1);
bool sgn(db x){
  return x>=0.0?0:1;
}
db cp(PII u,PII v){
  return (db)(u.fi*v.se-u.se*v.fi);
}
db len(PII u){
  return sqrt(u.fi*u.fi+u.se*u.se);
}
void f(PII x,PII y){
  PII tt2={y.fi-p.fi,y.se-p.se},tt3={x.fi-p.fi,x.se-p.se},tt1={-(tt3.se-tt2.se),tt3.fi-tt2.fi};
  db res1=len(tt2),res2=len(tt3),res3=abs((db)(tt1.fi*tt2.fi+tt1.se*tt2.se))/len(tt1);
  bool z=1;if(sgn(cp(tt1,tt2))==sgn(cp(tt1,tt3)))z=0;
  if(z){
    minn=min(minn,min(res1,min(res2,res3)));
    maxx=max(maxx,max(res1,max(res2,res3)));
  }else{
    minn=min(minn,min(res1,res2));
    maxx=max(maxx,max(res1,res2));
  }
}
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //這邊的PII必須是pair<ll,ll>
  cin>>n>>p.fi>>p.se;rep(i,0,n)cin>>ps[i].fi>>ps[i].se; prev=ps[0];
  rep(i,1,n)f(prev,ps[i]),prev=ps[i];
  f(prev,ps[0]);
  cout<<setprecision(20)<<pi*(maxx*maxx-minn*minn)<<'\n';
  return 0;
}

標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/613/submission/91112005)