题目传送门：http://pan.baidu.com/s/1nvKqStz
离线版题目：http://paste.ubuntu.com/18378190/
数据传送门：http://pan.baidu.com/s/1skSFZxr
哎呀，本来想着终于可以A题了！结果又被卡常QAQ，然后又只有60分QAQ
正解就是凸包+旋转卡壳+乱搞，然而原教的代码完全没有几何库，全部写进代码%%%%%%%，因此他天生自带小常数啊！
原教 Orz：http://paste.ubuntu.com/18378298/
哎呀，不想卡常了，贴一份代码水过就算了吧
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int MAXN = 8000+9;
const double EPS = 1e-8;
const double INF = 1e30;
double vout;
int n;
inline int cmp(double x){if (fabs(x)<EPS) return 0; else return (x>0)?1:-1;}
struct Point{
double x,y;
inline bool operator < (const Point &A) const {return (x < A.x) || (x == A.x && y < A.y);} inline bool operator == (const Point &A) const {return !cmp(x-A.x) && !cmp(y-A.y);} inline Point operator + (const Point &A) {Point tmp;tmp.x=x+A.x;tmp.y=y+A.y;return tmp;} inline Point operator - (const Point &A) {Point tmp;tmp.x=x-A.x;tmp.y=y-A.y;return tmp;} }p[MAXN],TMP[MAXN],ori[MAXN],SIZE[MAXN]; typedef Point Vector; inline double Cross(Vector A, Vector B){return A.x*B.y - A.y*B.x;} inline double Area2(Point A, Point B, Point C){return Cross(B-A, C-A);} inline bool Onleft(Point A, Point B, Point C){return cmp(Area2(A,B,C)) > 0;}
inline void CalArea(Point *A){
A[5] = A[1]; double ret = 0;
for (int i=1;i<=4;i++)
ret += Cross(A[i],A[i+1]);
vout = max(vout, fabs(ret));
}
inline int ConvexHull(Point *A, int N){
sort(A+1,A+1+N); int cnt=0;
for (int i=1;i<=N;i++){ while (cnt > 1 && !Onleft(TMP[cnt-1],TMP[cnt],A[i])) cnt--;
TMP[++cnt] = A[i];
} for (int i=N-1,lim=cnt;i;i--){
while (cnt > lim && !Onleft(TMP[cnt-1],TMP[cnt],A[i])) cnt--;
TMP[++cnt] = A[i];
}
if (cnt==4 && N==4) {
for (int i=1,tag;i<=4;i++){
tag = 0;
for (int j=1;j<cnt;j++)
if (A[i] == TMP[j]) tag = 1;
if (!tag) {A[4]=A[i];break;}
}
} for (int i=1;i<cnt;i++) A[i] = TMP[i];
return cnt-1;
}
inline void update(Point *A){
if (ConvexHull(A,4) == 4) CalArea(A);
else {
double sa = fabs(Area2(A[1],A[2],A[3]));
double mn = INF; A[5] = A[4]; A[4] = A[1];
for (int i=1;i<=3;i++) mn = min(mn, fabs(Area2(A[i],A[i+1],A[5])));
if (vout < sa-mn) vout = max(vout, sa-mn);
}
}
inline void cycle(int N){
for (int i=1;i<=N;i++) p[i+N] = p[i];
for (int i=1;i<=N;i++) p[i+N*2] = p[i];
for (int k=2;k<N;k++){
for (int i=1,itr1=2,itr2=i+k+1;i<=N;i++){
while (itr1 < i+k && fabs(Area2(p[i],p[itr1],p[i+k])) <= fabs(Area2(p[i],p[itr1+1],p[i+k]))) itr1++;
while (itr2 < i+N && fabs(Area2(p[i+k],p[itr2],p[i])) <= fabs(Area2(p[i+k],p[itr2+1],p[i]))) itr2++;
SIZE[1] = p[i]; SIZE[2] = p[itr1]; SIZE[3] = p[i+k]; SIZE[4] = p[itr2];
CalArea(SIZE);
}
}
}
int main(){
freopen("large.in","r",stdin);
freopen("large.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y),
ori[i] = p[i];
int tmp = ConvexHull(p,n);
if (tmp == 4) CalArea(p);
else if (tmp == 3) for (int i=1;i<=n;i++){
int t = 1;
for (int j=1;j<=3;j++)
if (p[j]==ori[i]) t=0;
if (t) p[4] = ori[i], update(p);
} else cycle(tmp);
printf("%.3lf",vout/2.0);
return 0;
}
唯一比较欣慰的，快4个月没有写过几何题了，居然还能写出来，还没怎么调试就过了。
You made some decent points there. I looked on the internet
to find out more about the issue and found most individuals will go along with your views on this site.
Fantastic beat ! I wish to apprentice while you amend your web site, how can i subscribe for a
blog website? The account helped me a acceptable deal.
I had been a little bit acquainted of this your broadcast offered bright clear idea
Hey are using WordPress for your blog platform?
I’m new to the blog world but I’m trying to get started and set up my own. Do you need any coding knowledge to make your own blog?
Any help would be greatly appreciated!
Howdy! I know this is kinda off topic but I’d figured I’d ask.
Would you be interested in trading links or maybe guest writing a blog article or vice-versa?
My blog goes over a lot of the same subjects as yours and I feel we could
greatly benefit from each other. If you happen to be interested feel free to shoot me
an email. I look forward to hearing from you! Superb blog by the way!
Have you ever thought about publishing an e-book or guest authoring on other blogs?
I have a blog centered on the same topics you discuss and would love to have you share
some stories/information. I know my audience would enjoy your work.
If you are even remotely interested, feel free to shoot me an e mail.
Hello it’s me, I am also visiting this website regularly,
this web site is really fastidious and the visitors are in fact sharing
fastidious thoughts.
Excellent beat ! I wish to apprentice even as you amend your
web site, how can i subscribe for a weblog web site?
The account helped me a applicable deal. I have been tiny bit familiar of this
your broadcast offered brilliant clear idea
What’s up i am kavin, its my first time to commenting anyplace, when i read this paragraph
i thought i could also create comment due to this sensible article.
Hey there! Quick question that’s completely
off topic. Do you know how to make your site mobile
friendly? My website looks weird when browsing from my apple iphone.
I’m trying to find a template or plugin that might
be able to fix this issue. If you have any suggestions, please share.
Appreciate it!
Hi i am kavin, its my first time to commenting anyplace, when i
read this post i thought i could also create comment due to this good paragraph.
Pretty great post. I simply stumbled upon your weblog and wished to say that I have really enjoyed browsing your blog posts. In any case I’ll be subscribing for your rss feed and I am hoping you write again very soon!
When someone writes an post he/she retains the idea of a user in his/her
brain that how a user can know it. Thus that’s why this piece of writing is outstdanding.
Thanks!
Hello all, here every person is sharing these kinds of familiarity, so it’s good to read this web site, and I
used to pay a quick visit this webpage everyday.
Hi there to every one, the contents present at this website are genuinely remarkable for people knowledge, well, keep
up the good work fellows.
Definitely consider that that you stated.
Your favourite justification seemed to be on the web the simplest factor to be mindful of.
I say to you, I certainly get irked at the same time as other folks think about issues that they just don’t understand about.
You managed to hit the nail upon the highest and defined out the entire thing without having side-effects , other people could
take a signal. Will likely be back to get more. Thanks
Thanks for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your next write ups thank you once again.
Hello everyone, it’s my first go to see at this web page, and post is in fact fruitful for me, keep up
posting these posts.
My brother suggested I might like this blog.
He was entirely right. This post truly made my day. You
cann’t imagine simply how much time I had spent for
this information! Thanks!
Ahaa, its nice discussion on the topic of this piece of writing here
at this web site, I have read all that, so at this time me also commenting here.
Hi there! I could have sworn I’ve visited your
blog before but after going through some of the articles
I realized it’s new to me. Anyways, I’m certainly pleased I came across it
and I’ll be bookmarking it and checking back often!
I like the valuable information you provide in your articles.
I’ll bookmark your weblog and check again here frequently.
I’m quite sure I’ll learn many new stuff right here!
Best of luck for the next!
Whats Happening i’m new to this, I stumbled upon this I’ve found It absolutely helpful and it has helped me out loads. I’m hoping to contribute & aid other users like its helped me. Great job.
wow, awesome blog.Really looking forward to read more. Awesome.