题意
平面上最开始只包含 3 个点, 然后还会依次出现 N 个点. 每新增一个点, 请你求出包含这些点的周长最小的多边形的面积.
思路
采用平衡树维护, 每次插入寻找前驱和后继, 然后添加节点即可.
注意本题有可能会出现三点共线的情况, 可以通过随机指定初始点来解决.
精度略有毒瘤之处.
代码
- #include <bits/stdc++.h>
- #include <cmath>
- using namespace std;
- namespace StandardIO {
- template<typename T> inline void read (T &x) {
- x=0;T f=1;char c=getchar();
- for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
- for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
- x*=f;
- }
- template<typename T> inline void write (T x) {
- if (x<0) putchar('-'),x=-x;
- if (x>=10) write(x/10);
- putchar(x%10+'0');
- }
- }
- using namespace StandardIO;
- namespace Solve {
- const int N=100100;
- int n;
- long long ans;
- struct node {
- long long x,y;
- long double rad;
- node () {}
- node (int _x,int _y):x(_x),y(_y){}
- node (int _x,int _y,long double _r):x(_x),y(_y),rad(_r){}
- node operator - (const node &a) {
- return node(x-a.x,y-a.y);
- }
- node operator + (const node &a) {
- return node(x+a.x,y+a.y);
- }
- long long operator * (const node &a) {
- return (x*a.y-y*a.x);
- }
- } a[N],S;
- long double X,Y;
- set<node> sexy;
- inline bool operator <(const node &x,const node &b) {
- return x.rad<b.rad;
- }
- inline long double rad (node x) {
- return (long double)atan2((x.y-S.y),(x.x-S.x));
- }
- inline node pre (node x) {
- if (sexy.count(x)) return x;
- set<node>::iterator it=sexy.lower_bound(x);
- if (it==sexy.begin()) it=sexy.end();
- return *(--it);
- }
- inline node suc (node x) {
- set<node>::iterator it=sexy.upper_bound(x);
- if (it==sexy.end()) it=sexy.begin();
- return *it;
- }
- inline long long Abs (long long a) {
- return (a>0)?a:-a;
- }
- inline long long calc (node x,node b) {
- return Abs(x*b);
- }
- inline void insert (node x) {
- if (sexy.size()<=2) {
- sexy.insert(x);
- return;
- }
- node l=pre(x),r=suc(x);
- if ((x-l)*(r-l)<=0) return;
- ans+=calc(x-l,r-l);
- while (1) {
- node tmp=pre(x);
- sexy.erase(tmp),l=pre(x);
- if ((x-l)*(l-tmp)>=0) {
- sexy.insert(tmp);
- break;
- }
- ans+=calc(tmp-x,l-x);
- }
- while (1) {
- node tmp=suc(x);
- sexy.erase(tmp),r=suc(x);
- if ((x-r)*(r-tmp)<=0) {
- sexy.insert(tmp);
- break;
- }
- ans+=calc(tmp-x,r-x);
- }
- sexy.insert(x);
- }
- inline void init () {
- long double J=(long double)1.92,Z=(long double)6.08,M=(long double)1.7;
- S=node((long double)((long double)a[1].x*J+(long double)a[2].x*Z+(long double)a[3].x*M)/(long double)(J+Z+M),(long double)((long double)a[1].y*J+(long double)a[2].y*Z+(long double)a[3].y*M)/(long double)(J+Z+M));
- insert(node(a[1].x,a[1].y,rad(a[1])));
- insert(node(a[2].x,a[2].y,rad(a[2])));
- insert(node(a[3].x,a[3].y,rad(a[3])));
- ans+=calc(a[1]-a[3],a[3]-a[2]);
- }
- inline void MAIN () {
- for (register int i=1; i<=3; ++i) read(a[i].x),read(a[i].y);
- init();
- read(n);
- for (register int i=4; i<=n+3; ++i) {
- read(a[i].x),read(a[i].y);
- insert(node(a[i].x,a[i].y,rad(a[i])));
- write(ans),putchar('\n');
- }
- }
- #undef int
- }
- int main () {
- Solve::MAIN();
- }
来源: http://www.bubuko.com/infodetail-3156466.html