C++ 解法, 执行用时: 89ms, 内存消耗: 14516K, 提交时间: 2022-02-28 12:58:39
#include<bits/stdc++.h>
#define ll long long
#define Pair pair<int,int>
using namespace std;
const int MAX = 3e5 + 10;
//const int INF32 = 0x3f3f3f3f;
const double EPS = 1e-5;
const double PI = acos(-1.0);
struct Point {
ll x, y;
Point(ll _x = 0, ll _y = 0) {
x = _x; y = _y;
}
friend Point operator + (const Point &a, const Point &b) {
return Point(a.x + b.x, a.y + b.y);
}
friend Point operator - (const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
}
friend double operator ^ (const Point &a, const Point &b) {
return a.x*b.y - a.y*b.x;
}
friend bool operator == (const Point &a, const Point &b) {
return fabs(a.x - b.x)<EPS&&fabs(a.y - b.y)<EPS;
}
};
Point Basic;
set<Point> Set;
typedef Point Vec;//向量
ll len(Vec v) { return sqrt(v.x*v.x + v.y*v.y); }
ll dis(Point A, Point B) { return len(A - B); }// 两点间的距离
// DEPENDS len, V-V
bool operator < (Point a, Point b) {//极角排序(第一关键字：角度，第二关键字：长度)
a = a - Basic; b = b - Basic;
double Ang1 = atan2(a.y, a.x), Ang2 = atan2(b.y, b.x);
ll Len1 = dis(a, Point(0.0, 0.0)), Len2 = dis(b, Point(0.0, 0.0));
if (fabs(Ang1 - Ang2)<EPS) return Len1<Len2;
return Ang1<Ang2;
}
set<Point>::iterator Pre(set<Point>::iterator it) { //
if (it == Set.begin()) it = Set.end();
return --it;
}
set<Point>::iterator Nxt(set<Point>::iterator it) {
++it;
return it == Set.end() ? Set.begin() : it;
}
int Query(Point p) { //询问，点p是否在凸包内(凸包用set实现的平衡树维护)
set<Point>::iterator it = Set.lower_bound(p);
if (it == Set.end()) it = Set.begin();
return ((p - *(Pre(it))) ^ (*(it)-*(Pre(it)))) < EPS;
}
Point mark[MAX];
ll ANS;
void Insert(Point p) { //插入一个点
if (Query(p)) return; //如果p在凸包内，直接返回，凸包不改变
Set.insert(p);
set<Point>::iterator it = Nxt(Set.find(p));//存it为在凸包内对应的下一个点
while (Set.size()>3 && ((p - *(Nxt(it))) ^ (*(it)-*(Nxt(it))))<EPS) {//(p,p+1)和(p+1,p+2)进行叉乘
Set.erase(it); it = Nxt(Set.find(p));
}
it = Pre(Set.find(p));
while (Set.size()>3 && ((p - *(it)) ^ (*(it)-*(Pre(it))))>-EPS) {
Set.erase(it); it = Pre(Set.find(p));
}
}
ll cross(Point a, Point b, Point c) {
return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}
void Addp(Point p) { //插入一个点
ll pos = 0;
int cnt = 0;
if (Query(p)) return; //如果p在凸包内，直接返回，凸包不改变
Set.insert(p);
set<Point>::iterator it = Nxt(Set.find(p));//存it为在凸包内对应的下一个点
pos += abs(cross(p, *(it), *(Pre(Set.find(p))))) ;
while (Set.size()>3 && ((p - *(Nxt(it))) ^ (*(it)-*(Nxt(it))))<EPS) {//(p,p+1)和(p+1,p+2)进行叉乘
mark[cnt++] = *(it);
pos += abs(cross(p, *(it), *(Nxt(it))));
Set.erase(it);
it = Nxt(Set.find(p));
}
it = Pre(Set.find(p));
while (Set.size()>3 && ((p - *(it)) ^ (*(it)-*(Pre(it))))>-EPS) {
mark[cnt++] = *(it);
pos += abs(cross(p, *(it), *(Pre(it)))) ;
Set.erase(it);
it = Pre(Set.find(p));
}
ANS = max(ANS, pos);
Set.erase(p);
for (int i = 0; i < cnt; i++) {
Set.insert(mark[i]);
}
}
ll getArea() {
ll sum = 0;
set<Point>::iterator it = Set.begin();
set<Point>::iterator iti = Nxt(it);
while (iti != Set.end()) {
sum += abs(cross(*(it), *(iti), *(Nxt(iti)))) ;
if (iti == Pre(Set.end())) {
break;
}
iti = Nxt(iti);
}
return sum;
}
bool cmp1(Point a, Point b) {
if (a.x != b.x)return a.x < b.x;
else return a.y < b.y;
}
int Andrew(int n, Point dian[], Point bao[]) { //求凸包，返回凸包大小+1
sort(dian, dian + n, cmp1);//排序
int top = 0;
for (int i = 0; i < n; i++) {
while (top > 1 && cross(bao[top - 2], bao[top - 1], dian[i]) <= 0)top--;//踢出前一个
bao[top++] = dian[i]; //该点在向量左边，直接入栈
}
int k = top;
for (int i = n - 2; i >= 0; i--) {
while (top > k&&cross(bao[top - 2], bao[top - 1], dian[i]) <= 0)
top--;
bao[top++] = dian[i];
}
return top;
}
Point pp[MAX];
Point bao[MAX];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> pp[i].x >> pp[i].y;
}
Basic = Point(0, 0);
for (int i = 0; i < 3; ++i) {
Basic = Basic + pp[i];
}
Basic.x /= 3.0; Basic.y /= 3.0;
for (int i = 0; i < 3; i++) {
Set.insert(pp[i]);
}
for (int i = 3; i < k; ++i) {
if (i >= k-1)break;
Insert(pp[i]);
}
ll ans = getArea();
int top = Andrew(n, pp, bao);
//for (int i = k; i < n; i++)Addp(pp[i]);
for (int i = 0; i < top; i++)Addp(bao[i]);
ans += ANS;
cout << (ans >> 1);
if (ans & 1)cout << ".5\n";
else cout << ".0\n";
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 53ms, 内存消耗: 2324K, 提交时间: 2022-09-07 11:25:28
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
using _T = ll;
const _T eps = 0;
const int MAXN = 1e5 + 5;
template<typename T> struct tpoint
{
T x,y;
tpoint(T x,T y):x(x),y(y){};
tpoint(){};
bool operator == (const tpoint &p) const { return x==p.x && y==p.y; }
bool operator < (const tpoint &p) const { if(x==p.x) return y<p.y; return x<p.x; }
tpoint operator - (const tpoint &p) const { return tpoint(x-p.x,y-p.y); }
T operator ^ (const tpoint &p) const { return x*p.y-p.x*y; }
int toleft (const tpoint &p) const { auto t=(*this)^p; return (t>eps)-(t<-eps); }
void show() { printf("point: %lld %lld\n",x,y); }
};
using point = tpoint<_T>;
point p;
ll m;
vector<point> points,convexs;
ll nxt(ll i) { return i%m+1; }
ll pre(ll i) { return (i+m-2)%m+1; }
ll cvxs[MAXN],cvxind[MAXN];
bool cmp(ll x, ll y) { return points[x] < points[y]; }
ll convexhall(ll n)
{
ll i,k,a,sz=0;
for(i=1;i<=n;i++) cvxind[i] = i;
sort(cvxind+1,cvxind+1+n,cmp);
for(i=1;i<=n;i++)
{
a = cvxind[i]; p = points[a];
while(sz>1 && (points[cvxs[sz-1]]-points[cvxs[sz-2]]).toleft(p-points[cvxs[sz-2]]) <= 0) sz --;
cvxs[sz++] = a;
}
k = sz;
for(i=max(n-1,1ll);i>=1;i--)
{
a = cvxind[i]; p = points[a];
while(sz>k && (points[cvxs[sz-1]]-points[cvxs[sz-2]]).toleft(p-points[cvxs[sz-2]]) <= 0) sz --;
cvxs[sz++] = a;
}
convexs.resize(sz+1);
for(i=1;i<=sz;i++) convexs[i] = points[cvxs[i-1]];
return sz-1;
}
ll sum[MAXN];
bool pinconvex(vector<point> &convexs, ll n, point p)
{
ll st = 2, en = n-1, half,x,y;
point p0 = convexs[1];
while(en >= st)
{
half = en + (st -en) / 2;
x = (convexs[half]-p0).toleft(p-p0);
y = (convexs[half+1]-p0).toleft(p-p0);
if(x >= 0 && y <= 0)
{
if((convexs[half+1]-convexs[half]).toleft(p-convexs[half]) >= 0) return 1;
return 0;
}
else if(x >= 0 && st != en) st = half;
else en = half - 1;
}
return 0;
}
ll cutdir(vector<point> &convexs, ll m, point &p, ll dir)
{
point v0;
if(dir == 1) v0 = convexs[1]-p;
else v0 = p-convexs[1];
ll d0 = (v0.toleft(convexs[2]-convexs[1]) >= 0);
if(d0 && v0.toleft(convexs[1]-convexs[m]) <= 0) return 1;
ll st = 1, en = m, half,d;
while(en > st)
{
half = st + (en - st) / 2;
d = (dir*(convexs[half]-p).toleft(convexs[half+1]-convexs[half]) >= 0);
//printf("%lld %lld %lld\n",half,d,d0);
if(d0 == d)
{
if(v0.toleft(convexs[half]-convexs[1]) > 0) d = 1-d;
}
if(!d) st = half + 1;
else en = half;
}
return en;
}
pair<ll,ll> cutline(vector<point> &convexs, ll m, point &p)
{
ll a,b;
//printf("dir: in!\n");
a = cutdir(convexs,m,p,-1);
//printf("dir: out!\n");
b = cutdir(convexs,m,p,1);
return make_pair(a,b);
}
int main()
{
ll n,i,k,ans=0,ans1,ans2;
scanf("%lld%lld",&n,&k);
points.resize(n+1);
for(i=1;i<=n;i++) scanf("%lld%lld",&points[i].x,&points[i].y);
m = convexhall(k);
for(i=1;i<=m;i++)
{
sum[i] = (convexs[i] ^ convexs[i+1]) + sum[i-1];
//convexs[i].show();
}
ans = sum[m];
//printf("%lld\n",ans);
for(i=k+1;i<=n;i++)
{
if(pinconvex(convexs,m,points[i])) continue;
//printf("no in! %lld\n",i);
pair<ll,ll> pa = cutline(convexs,m,points[i]);
//printf("%lld %lld\n",pa.first,pa.second);
if(pa.first > pa.second) ans1 = sum[pa.first-1] - sum[pa.second-1];
else ans1 = sum[m] - (sum[pa.second-1] - sum[pa.first-1]);
ans2 = (convexs[pa.first]^points[i]) + (points[i]^convexs[pa.second]);
ans = max(ans,ans1+ans2);
}
printf("%lld",ans/2);
if(ans%2) printf(".5");
else printf(".0");
return 0;
}
out of 
trees in the Dark Forest. What is the highest power you can achieve by gaining control over a single additional tree somewhere in the forest?.
and
specifying the locations of the
trees do not