題意：計(jì)算多邊形核的面積。

分析：半平面交的模板。有兩個(gè)問題要注意，1.題目沒說多邊形點(diǎn)的順序是順時(shí)針還是逆時(shí)針，要先用面積的正負(fù)來判斷點(diǎn)的順序。2.題目中說坐標(biāo)都在16位整數(shù)范圍內(nèi)，也就是說半平面交模板中初始的無限大平面的四個(gè)頂點(diǎn)設(shè)為±1e5就可以了，原本設(shè)為±1e15無限WA。

?

#include <cstdio> #include <algorithm> #define vector point using std::swap; struct point {double x,y;point(double xx = 0,double yy = 0){x = xx;y = yy;}point operator - (const point& s){return point(x - s.x, y - s.y);}point operator + (const point& s){return point(x + s.x,y + s.y);} }; struct polygon {point p[2000];int size; }; struct line {point first,second;line(point p1 = point(),point p2 = point()){first = p1;second = p2;} };double cross_product(vector v1,vector v2) {return v1.x * v2.y - v1.y * v2.x; }//求兩直線交點(diǎn) point line_intersection(line ln1,line ln2) {double a1,b1,c1,a2,b2,c2;a1 = ln1.first.y - ln1.second.y;b1 = ln1.second.x - ln1.first.x;c1 = ln1.first.x * ln1.second.y - ln1.second.x * ln1.first.y;a2 = ln2.first.y - ln2.second.y;b2 = ln2.second.x - ln2.first.x;c2 = ln2.first.x * ln2.second.y - ln2.second.x * ln2.first.y;double d = a1 * b2 - a2 * b1;return point((b1 * c2 - b2 * c1) / d,(c1 * a2 - c2 * a1) / d); }//一個(gè)多邊形與一個(gè)半平面的交集 polygon hpi(polygon& poly,line& ln) {int m = 0;polygon hull;point p1 = ln.first,p2 = ln.second;//窮舉多邊形的所有點(diǎn)，判斷是否在半平面上//如果凸多邊形hull與直線ln有交點(diǎn)就求交點(diǎn)for(int i = 0;i < poly.size;i++){double c = cross_product(p2 - p1,poly.p[i] - p1);double d = cross_product(p2 - p1,poly.p[(i + 1) % poly.size] - p1);//點(diǎn)poly.p[i]在半平面上if(c >= 0)hull.p[m++] = poly.p[i];//有交點(diǎn)if(c * d < 0)hull.p[m++] = line_intersection(line(poly.p[(i + 1) % poly.size],poly.p[i]),ln);}hull.size = m;return hull; }//poly的頂點(diǎn)順時(shí)針 bool polygon_kernel(polygon& poly,polygon& knl) {//初始化核為無限大knl.p[0] = point(-1e5,-1e5);knl.p[1] = point(1e5,-1e5);knl.p[2] = point(1e5,1e5);knl.p[3] = point(-1e5,1e5);knl.size = 4;line ln;point pre = poly.p[0];for(int i = 1;i <= poly.size;i++){ln.first = poly.p[i % poly.size];ln.second = poly.p[i - 1];knl = hpi(knl,ln);if(knl.size == 0)return false;}return true; }double polygon_area(polygon& poly) {double s = 0;for(int i = 0;i < poly.size - 1;i++)s += cross_product(poly.p[i],poly.p[i + 1]);s += cross_product(poly.p[poly.size - 1],poly.p[0]);return s / 2; }int main() {int t,n;polygon gallery,kernel;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i = 0;i < n;i++)scanf("%lf%lf",&gallery.p[i].x,&gallery.p[i].y);gallery.size = n;if(!polygon_kernel(gallery,kernel)){int left = 0,right = n - 1;while(left < right)swap(gallery.p[left++],gallery.p[right--]);polygon_kernel(gallery,kernel);}double s;s = polygon_area(kernel);printf("%.2lf\n",s);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ZShogg/archive/2013/05/07/3064859.html

總結(jié)

以上是生活随笔為你收集整理的poj1279的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。