| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 130427 |
2019-07-15T07:51:39 Z |
임유진(#3151) |
Fence (CEOI08_fence) |
C++14 |
|
2 ms |
376 KB |
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 105
#define fi first
#define se second
typedef pair<int, int> pii;
int N, M;
pii h[MAXN], t[MAXN];
vector<pii> ch;
int ccw(pii a, pii b, pii c) {
return a.fi * b.se - a.se * b.fi + b.fi * c.se - b.se * c.fi + c.fi * a.se - c.se * a.fi;
}
bool chkin(pii a, pii b, pii c, pii d) {
return ccw(a, b, d) > 0 && ccw(b, c, d) > 0 && ccw(c, a, d) > 0;
}
bool chktree(pii a, pii b, pii c) {
for(int i = 0; i < M; i++) if(chkin(a, b, c, t[i])) return true;
return false;
}
int main() {
scanf("%d%d", &N, &M);
for(int i = 0; i < N; i++) scanf("%d%d", &h[i].fi, &h[i].se);
for(int i = 0; i < M; i++) scanf("%d%d", &t[i].fi, &t[i].se);
sort(h, h + N);
vector<pii> lc, uc;
lc.push_back(h[0]);
lc.push_back(h[1]);
for(int i = 2; i < N; i++) {
while(lc.size() > 1 && ccw(lc[lc.size() - 2], lc.back(), h[i]) <= 0) lc.pop_back();
lc.push_back(h[i]);
}
uc.push_back(h[0]);
uc.push_back(h[1]);
for(int i = 2; i < N; i++) {
while(uc.size() > 1 && ccw(uc[uc.size() - 2], uc.back(), h[i]) >= 0) uc.pop_back();
uc.push_back(h[i]);
}
ch.insert(ch.end(), lc.begin(), lc.end());
for(int i = uc.size() - 2; i > 0; i--) ch.push_back(uc[i]);
for(int i = 0; i < N && ch.size() > 2; i++) {
vector<pii> v;
if(!chktree(ch.back(), ch[0], ch[1])) {
v.insert(v.end(), ch.begin() + 1, ch.end());
swap(v, ch);
continue;
}
if(!chktree(ch[ch.size() - 2], ch.back(), ch[0])) {
ch.pop_back();
continue;
}
for(int j = 1; j < ch.size() - 2; j++) {
if(!chktree(ch[j - 1], ch[j], ch[j + 1])) {
v.insert(v.end(), ch.begin(), ch.begin() + j);
v.insert(v.end(), ch.begin() + j + 1, ch.end());
swap(v, ch);
break;
}
}
}
if(ch.size() < 3) {
printf("%d", 111 * M);
return 0;
}
int cnt = 0;
for(int i = 0; i < M; i++) {
if(ccw(t[i], ch.back(), ch[0]) < 0) {
cnt++;
continue;
}
for(int j = 0; j < ch.size() - 1; j++) if(ccw(t[i], ch[j], ch[j + 1]) < 0) {
cnt++;
break;
}
}
printf("%d", 111 * cnt + 20 * int(ch.size()));
return 0;
}
Compilation message
fence.cpp: In function 'int main()':
fence.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 1; j < ch.size() - 2; j++) {
~~^~~~~~~~~~~~~~~
fence.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < ch.size() - 1; j++) if(ccw(t[i], ch[j], ch[j + 1]) < 0) {
~~^~~~~~~~~~~~~~~
fence.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
fence.cpp:32:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < N; i++) scanf("%d%d", &h[i].fi, &h[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fence.cpp:33:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < M; i++) scanf("%d%d", &t[i].fi, &t[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
