【BZOJ 2618】[CQOI2006] 凸多边形

Qizy 几何, 半平面交, 解题报告

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2618
神犇题解：http://hzwer.com/4713.html

解题报告

把每一个凸多边形看成一堆半平面
于是原题变成求半平面交

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;
const double EPS = 1e-8;

int n,m;

struct Point{
	double x,y;
	inline Point() {}
	inline Point(double a, double b):x(a),y(b) {}
	inline Point operator + (const Point &P) const {return Point(x+P.x, y+P.y);}
	inline Point operator - (const Point &P) const {return Point(x-P.x, y-P.y);}
	inline Point operator * (double d) const {return Point(x*d, y*d);}
	inline Point operator / (double d) const {return Point(x/d, y/d);}
	inline double operator * (const Point &P) const {return x*P.x + y*P.y;}
	inline double operator ^ (const Point &P) const {return x*P.y - P.x*y;} 
}p[N],cvx[N];

struct Line{
	Point a,b; double slp;
	inline Line() {}
	inline Line(const Point &x, const Point &y) {a = x; b = y; slp = atan2(b.y-a.y, b.x-a.x);}
	inline bool operator < (const Line &L) const {return slp < L.slp - EPS || (fabs(slp-L.slp) < EPS && ((b-a)^(L.b-a)) < -EPS);}
	inline bool operator != (const Line &L) {return fabs(slp - L.slp) > EPS;}
	inline bool onleft(const Point &P) {return ((b - a) ^ (P - a)) > EPS;}
	inline double len() {return sqrt((b - a) * (b - a));}
	inline Point ins(const Line &L) {
		double s1 = (b - L.b) ^ (L.a - L.b);
		double s2 = (a - L.a) ^ (L.b - L.a);
		return a + (((b - a) * s2) / (s1 + s2));
	}
}l[N],que[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void HalfPlaneIntersection(int tot, Line *a, int &cnt, Line *b, Point *c) {
	sort(a+1, a+1+tot); cnt = tot; tot = 1; 
	for (int i=2;i<=cnt;i++) if (a[i] != a[i-1]) a[++tot] = a[i]; 
	b[1] = a[1]; b[2] = a[2]; int l=1,r=2;
	for (int i=3;i<=tot;i++) {
		while (l < r && !a[i].onleft(b[r-1].ins(b[r]))) r--;
		while (l < r && !a[i].onleft(b[l].ins(b[l+1]))) l++;
		b[++r] = a[i];
	} 
	while (l < r && !b[l].onleft(b[r].ins(b[r-1]))) r--;
	while (l < r && !b[r].onleft(b[l].ins(b[l+1]))) l++;
	cnt = 0; b[0] = b[r];
	for (int i=l;i<=r;i++) b[++cnt] = b[i];
	for (int i=1;i<=cnt;i++) c[i] = b[i].ins(b[i-1]); 
}

int main() {
	n = read(); int tot=0,cnt=0;
	for (int i=1;i<=n;i++) {
		m = read();
		for (int j=1;j<=m;j++) p[j].x = read(), p[j].y = read();
		p[m+1] = p[1];
		for (int j=1;j<=m;j++) l[++tot] = Line(p[j], p[j+1]);
	}
	HalfPlaneIntersection(tot, l, cnt, que, cvx);
	double vout = 0;
	for (int i=2;i<cnt;i++) vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]);
	printf("%.3lf\n",vout/2);
	return 0;
}

21 thoughts to “【BZOJ 2618】[CQOI2006] 凸多边形”

  3. Hi, I believe your web site may be having internet browser compatibility issues.
    When I look at your website in Safari, it looks fine however when opening in IE,
    it’s got some overlapping issues. I merely wanted
    to give you a quick heads up! Besides that, wonderful website!

    Reply

  4. You’re so interesting! I do not believe I’ve truly read through
    anything like that before. So nice to discover someone with genuine thoughts on this topic.
    Really.. thanks for starting this up. This web site is one thing that
    is required on the internet, someone with a bit of originality!

    Reply

  5. Thank you, I’ve just been searching for info approximately this topic for
    a while and yours is the greatest I’ve discovered so far.
    However, what concerning the conclusion? Are you sure concerning the supply?

    Reply

  9. Howdy are using WordPress for your site platform? I’m new to the blog world but I’m
    trying to get started and create my own. Do you require any html coding knowledge to make
    your own blog? Any help would be greatly appreciated!

    Reply

  10. I like the helpful information you supply for your articles.

    I’ll bookmark your blog and test again right here regularly.

    I am relatively sure I’ll be told lots of new stuff proper right here!
    Best of luck for the following!

    Reply

  11. Greetings from Florida! I’m bored at work so I decided to check out your site on my iphone during lunch break.
    I enjoy the knowledge you provide here and can’t wait to
    take a look when I get home. I’m shocked at how fast your blog loaded on my phone ..
    I’m not even using WIFI, just 3G .. Anyhow, superb blog!

    Reply

  15. Does your blog have a contact page? I’m having a tough time locating it
    but, I’d like to shoot you an email. I’ve got some suggestions for your blog you might be interested in hearing.
    Either way, great site and I look forward to seeing it expand over time.

    Reply

  18. Greetings I am so grateful I found your blog page, I really found you by accident, while I was researching on Google for something else, Anyhow I
    am here now and would just like to say thank you for a tremendous post and a
    all round thrilling blog (I also love the theme/design), I
    don’t have time to browse it all at the moment but I have saved it and also included your RSS feeds, so when I have
    time I will be back to read more, Please do keep up the fantastic work.

    Reply

  20. After looking over a number of the blog posts on your web site, I really like your technique of blogging.
    I added it to my bookmark website list and will be checking
    back soon. Please visit my web site too and tell
    me what you think.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *