Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:确实水题一个

Posted by 781778304 at 2011-08-08 12:16:38 on Problem 1828
In Reply To:确实水题一个 Posted by:781778304 at 2011-08-08 12:16:15
> dp+sort
#include<iostream>
#include<algorithm>
using namespace std;
#define N 50005
typedef struct Point 
{
	int x;
	int y;
}o;
Point p[N];
bool cmp(Point a,Point b)
{
	return a.x>b.x||a.x==b.x&&a.y>b.y;
}
int main()
{
	int n,i;
	while(1)
	{
		cin>>n;
		if(n==0)break;
		for(i=0;i<n;i++)
			cin>>p[i].x>>p[i].y;
		sort(p,p+n,cmp);
		int count=1;
		int max_x=p[0].x;
		int max_y=p[0].y;
		for(i=1;i<n;i++)
		{
			if(p[i].x>max_x)
			{
				max_x=p[i].x;
				count++;
			}
			else if(p[i].y>max_y)
			{
				max_y=p[i].y;
				count++;
			}
		}
		cout<<count<<endl;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator