ZOJ 3511 不相交切切多边形线段树求最大边数

题意：

n多凸边形 m刀（把n切m刀，问切完后的图形中最多的边数是多少）

切a点-b点

数据保证切的刀不会相交

思路：

2点之间的剩余点数就是边数，

把a-b距离近排序

切完一刀就统计一下切出来的蛋糕的边数，并舍弃

[a,b] 表示a,b 点间剩下的点数(就是边数)

先计算[a,b]的点数, 然后删除(a,b) 区间的点 (注意删除的是(a,b) ,所以实际操作是删除[a,b] )

最后要特殊算下剩下那块的(因为那块没有切)

#include<iostream>

#include<stdio.h>

#include<string>

#include<string.h>

#include<algorithm>

#include<set>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <math.h>

#include <queue>

#define N 10100

#define M 2000100

#define inf64 0x7ffffff

#define inf 1073741824

#define ll int

#define L(x) x<<1

#define R(x) x<<1|1

#define Mid(x,y) (x+y)>>1

using namespace std;

inline ll Min(ll a,ll b){return a>b?b:a;}

inline ll Max(ll a,ll b){return a>b?a:b;}  

struct Point{

	int x,y,dis;

}p[N];

bool cmp(Point a,Point b){

	return a.dis<b.dis;

}

struct node{

    int l,r;

    ll sum;

}tree[N*4];  

void pushup(int id){

	tree[id].sum = tree[R(id)].sum + tree[L(id)].sum;

}

void build(int l,int r,int id){

	tree[id].l = l, tree[id].r = r;

	tree[id].sum = r - l + 1;

	if(l == r)return ;

	int mid = Mid(l,r);

	build( l, mid, L(id));

	build( mid+1, r, R(id));

}

void updata(int l, int r,int id){

	if(l == tree[id].l && tree[id].r == r)

	{ tree[id].sum = 0; return ;}

	int mid=Mid(tree[id].l, tree[id].r);

	if(r <= mid)updata(l, r, L(id));

	else if(mid < l) updata(l, r, R(id));

	else

	{

		updata(l, mid, L(id));

		updata(mid+1, r, R(id));

	}

	pushup(id);

}

int query(int l, int r, int id){

	if(tree[id].sum==0)return 0;

	if( tree[id].l == tree[id].r)return tree[id].sum;

	int mid=Mid(tree[id].l, tree[id].r);

	if(r <= mid)

		return query(l, r, L(id));

	if(mid < l )

		return query(l, r, R(id));

	return query(l, mid, L(id)) + query(mid+1, r, R(id));

}

int main(){

	int n, m, i,temp;

	while(~scanf("%d %d",&n,&m)){

		for(i=1;i<=m;i++){

			scanf("%d %d",&p[i].x,&p[i].y);

			if(p[i].x>p[i].y)

				temp=p[i].x, p[i].x=p[i].y, p[i].y=temp;

			p[i].dis=p[i].y-p[i].x;

		}

		sort(p+1, p+m+1, cmp);

		build(1,n,1);

		int ans=0;

		for(i=1;i<=m;i++){

			ans=Max(ans, query(p[i].x, p[i].y, 1));

			updata(p[i].x+1, p[i].y-1, 1);

		}

		ans=Max(ans, query(1,n,1));

		printf("%d\n",ans);

	}

	return 0;

}

/*

6 3

1 5

1 4

1 3

ans:

3

*/

巴特西

ZOJ 3511 不相交切切多边形线段树求最大边数

最新文章

热门文章

巴特西

ZOJ 3511 不相交切切多边形 线段树求最大边数

最新文章

热门文章

ZOJ 3511 不相交切切多边形线段树求最大边数