参考例题：http://www.lydsy.com/JudgeOnline/problem.php?id=2618
参考资料：http://foenix.top/2015/03/17/半平面交nlogn方法小结/
备注：这份代码不能处理退化成一个点或一条线的情况，如果实在要处理这种情况，请自行将直线平移适当距离
#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);
Point tmp = a + (((b - a) * s2) / (s1 + s2));
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;
}
Hello it’s me, I am also visiting this site regularly, this web page
is genuinely good and the visitors are in fact sharing pleasant thoughts.
Nice post. I was checking continuously this blog and I’m impressed!
Extremely helpful info particularly the last part :
) I care for such info much. I was seeking this certain info for a long time.
Thank you and good luck.
Hello Dear, are you in fact visiting this site on a regular basis, if so after that you will
definitely obtain fastidious experience.
This is the perfect blog for everyone who wishes to
find out about this topic. You realize so much its almost hard to argue with you (not that I actually will
need to…HaHa). You definitely put a fresh spin on a subject that has been written about for decades.
Wonderful stuff, just great!
Today, I went to the beach with my kids. I found a sea
shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She
put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear.
She never wants to go back! LoL I know this is completely off topic but I had to tell someone!
Definitely imagine that which you stated. Your favourite
reason appeared to be at the web the easiest thing to take into
accout of. I say to you, I definitely get annoyed at the same time as people think about
concerns that they just don’t know about.
You controlled to hit the nail upon the highest
and also outlined out the entire thing with no need side-effects
, people could take a signal. Will likely be again to get more.
Thanks
Hey! This is my first visit to your blog! We are a team of
volunteers and starting a new project in a community in the same niche.
Your blog provided us valuable information to work on. You have done a
marvellous job!
You’ve made some decent points there. I looked on the web to learn more about
the issue and found most individuals will go along with your views on this website.
Thanks very nice blog!
Great awesome things here. I?¦m very happy to look your post. Thank you a lot and i’m having a look ahead to touch you. Will you kindly drop me a mail?
What’s Happening i am new to this, I stumbled upon this I’ve found It absolutely useful and it has helped me out loads.
I hope to contribute & assist other customers like its aided me.
Good job.
Just wish to say your article is as surprising. The clearness in your post
is just spectacular and i could assume you are an expert on this subject.
Fine with your permission let me to grab your feed to keep up to date with forthcoming post.
Thanks a million and please keep up the rewarding work.
Hello to every one, the contents present at this
web site are truly awesome for people knowledge, well, keep up the good work fellows.
Every weekend i used to pay a visit this website, because
i want enjoyment, since this this web site conations
truly pleasant funny material too.
Fascinating blog! Is your theme custom made or did you download it from
somewhere? A theme like yours with a few simple tweeks would really make my blog shine.
Please let me know where you got your theme. Thank you
Simply wish to say your article is as astounding.
The clearness to your post is just great and i can think you are an expert
on this subject. Well together with your permission allow me to snatch your RSS feed to keep updated with imminent post.
Thanks 1,000,000 and please keep up the enjoyable work.
Good web site you have got here.. It’s hard to find high-quality writing like yours these days.
I really appreciate individuals like you! Take care!!
Hey very nice website!! Man .. Excellent .. Wonderful ..
I’ll bookmark your site and take the feeds also?
I am satisfied to search out numerous useful information right here in the post,
we’d like develop extra techniques in this
regard, thank you for sharing. . . . . .
Howdy just wanted to give you a brief heads up and let you know a few
of the pictures aren’t loading properly. I’m not sure why but I think its a linking issue.
I’ve tried it in two different web browsers and both show the same results.
Hello, I would like to subscribe for this webpage to obtain newest
updates, so where can i do it please help.
When someone writes an article he/she keeps the plan of
a user in his/her brain that how a user can understand it.
Therefore that’s why this piece of writing is amazing.
Thanks!
Thanks very interesting blog!
My brother suggested I would possibly like this web site. He was once totally right. This publish actually made my day. You cann’t imagine just how so much time I had spent for this information! Thank you!