ZOJ3511 Cake Robbery, 폭력

2164 단어 email
하나의 볼록 포켓은 정점이 있는 만큼 모서리가 있다.
칼자국은 내고 싶지 않기 때문에 모든 칼에 대해 기존의 모든 돌출된 가방을 하나하나 열거하고 도대체 어느 다각형에 떨어졌는지 한 다음에 이 다각형을 두 개로 나누면 된다.
/*******************************************************************************
 # Author : Neo Fung
 # Email : [email protected]
 # Last modified: 2012-07-11 19:18
 # Filename: ZOJ3511 Cake Robbery.cpp
 # Description : 
 ******************************************************************************/
#ifdef _MSC_VER
#define DEBUG
#define _CRT_SECURE_NO_DEPRECATE
#endif

#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
#include <vector>
using namespace std;

const int kMAX=100010;
vector<int> vec[kMAX];
int array[kMAX];

int main(void)
{
#ifdef DEBUG  
  freopen("../stdin.txt","r",stdin);
  freopen("../stdout.txt","w",stdout); 
#endif  

  int n,m;
	int x,y;

  while(~scanf("%d%d",&n,&m) && n)
  {
		vec[0].clear();
		for(int i=1;i<=n;++i)
			vec[0].push_back(i);

		int total=1;
		while(m--)
		{
			scanf("%d%d",&x,&y);
			if(x>y) swap(x,y);
			for(int i=0;i<total;++i)
			{
				int cnt=0,beg,end;
				for(size_t j=0;j<vec[i].size();++j)
				{
					if(x==vec[i][j])
					{
						beg=j;
						++cnt;
					}
					if(y==vec[i][j])
					{
						end=j;
						++cnt;
					}
				}
				if(cnt==2)
				{
					if(beg==end-1 || (end+1)%vec[i].size()==beg)
						break;// , 
          vec[total].clear();
					for(size_t k=beg;k<=end;++k)
						vec[total].push_back(vec[i][k]);
					total++;

					int idx=0;
					for(size_t k=0;k<=beg;++k)
						array[idx++]=vec[i][k];
					for(size_t k=end;k<vec[i].size();++k)
						array[idx++]=vec[i][k];
					vec[i].clear();
					vec[i].assign(array,array+idx);
          break;
				}
			}
		}
		size_t ans=0;
		for(int i=0;i<total;++i)
			ans=max(ans,vec[i].size());
		printf("%d
",ans); } return 0; }

좋은 웹페이지 즐겨찾기