YACS20225月-数山峰

题目描述

在平面直角坐标系上有n 座像山峰一样的图案。每座山峰是一个直角等腰三角形，它们的底边都是坐标系的X轴，它们的峰顶在第一象限里，其中第 i 座山峰的峰顶坐标为(xi,yi)。

如果一座山峰的一部分在另一座山峰的内部，那么这两部分山峰就重叠了。给定每个山峰的峰顶坐标，请统计不重复计算重叠部分的前提下，这些山峰的总面积是多少。

输入格式

第一行：单个整数 n；

第二行到第 n+1 行：第 i+1 行两个整数，表示一个峰顶的坐标 xi 与 yi。

输出格式

单个整数：设所有的山峰的可见面积为 s，因为希望输出整数，所以规定输出 4s。

28444304-1590c808a6bbe589.png

第一种情况，两个三角形面积相加减去中间部分；第二种情况，两个相加；第三种情况直接加一个三角形面积。

接下来，就是研究xi yi之间的关系，确定三角形的状态。

1：左端点比上一个左端点大，但比上一个右端点小

2：左端点大于等于上一个右端点，这是完全独立

3：左端点比上一个左端点大，比上一个右端点小，这是包含

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+5;

struct node{

  ll x,y;

  ll lft,rgt;

  inline bool operator<(const node& o)const{return lft<o.lft;}

};

node datas[maxn];

int n;

int main(){

ios::sync_with_stdio(false);

  cin>>n;

  for (int i=1;i<=n;i++){

  cin>>datas[i].x>>datas[i].y;

    datas[i].lft=datas[i].x-datas[i].y;

    datas[i].rgt=datas[i].x+datas[i].y;

  }

  sort(datas+1,datas+1+n);

  ll ans=datas[1].y*datas[1].y*4;

  int las=1;

  for (int i=2;i<n;i++){

  if (datas[i].lft>=datas[las].rgt){

  ans+=datas[i].y*datas[i].y*4;

    las=i;

  }else if(datas[i].lft<datas[las].rgt&&datas[i].rgt>datas[las].rgt){

  ll a=datas[las].rgt-datas[i].lft;

    ans=ans-a*a;

    ans=ans+datas[i].y*datas[i].y*4;

    las=i;

  }

  }

cout<<ans<<endl;

  return 0;

}